Pagini recente » Cod sursa (job #481231) | Cod sursa (job #2034865) | Cod sursa (job #3246960) | Cod sursa (job #1999796) | Cod sursa (job #2299799)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
constexpr int NMAX=2e6+5;
char A[NMAX], B[NMAX];
int N, M, i, j, PHI[NMAX];
int Sol[NMAX], vf;
void Precalculation ()
{
strcat(A, "#");
strcat(A, B);
N=strlen(A);
int ans=0;
for(i=1; i<N; ++i)
{
while(ans && A[ans] != A[i])
ans=PHI[ans-1];
if(A[ans] == A[i])
++ans;
PHI[i]=ans;
}
}
void Match ()
{
for(int i=M+1; i<N; ++i)
if(PHI[i] == M)
Sol[++vf]=i-M+1;
}
void Afis ()
{
g<<vf<<'\n';
for(int i=1; i<=min(vf, 1000); ++i)
g<<Sol[i]-M-1<<' ';
g<<'\n';
}
int main()
{
f.tie(NULL);
f>>A>>B;
M=strlen(A);
Precalculation();
Match();
Afis();
return 0;
}