Pagini recente » Cod sursa (job #582308) | Cod sursa (job #2008167) | Cod sursa (job #2171818) | Cod sursa (job #2215142) | Cod sursa (job #584770)
Cod sursa(job #584770)
#include<fstream>
#include<cstdio>
using namespace std;
const int MaxN = 2000005;
const int MaxP = 1000;
const char InFile[] = "strmatch.in";
const char OutFile[] = "strmatch.out";
int N,M,urm[MaxN],sol[MaxP+1];
char A[MaxN],B[MaxN];
void KMP()
{
int i,q,k;
urm[1] = 0;
k = 0;
for( q = 2 ; q <= M ; q++ )
{
while( k && B[q] != B[k+1] )
k = urm[k];
if( B[q] == B[k+1] )
++k;
urm[q] = k;
}
q = M+1;
for( i = 1 ; i <= N ; i++ )
{
while( q && A[i] != B[q+1] )
q = urm[q];
if( B[q+1] == A[i] )
++q;
if( q == M )
{
++sol[0];
if( sol[0] > MaxP )
continue;
sol[sol[0]] = i-M;
}
}
}
int main()
{
ifstream fin ( InFile );
ofstream fout ( OutFile );
fin.getline(B+1,MaxN);
fin.getline(A+1,MaxN);
fin.close();
N = strlen(A+1);
M = strlen(B+1);
KMP();
fout << sol[0] << '\n';
for( int i = 1 ; i <= sol[0] && i <= MaxP ; i++ )
fout << sol[i] << ' ';
fout << '\n';
fout.close();
return 0;
}