Pagini recente » Cod sursa (job #2103660) | Cod sursa (job #3148362) | Cod sursa (job #471393) | Cod sursa (job #677399) | Cod sursa (job #1159050)
#include <fstream>
#include <string.h>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i,p[2000001],q,n,m,s[2000001],nr;
char x,A[2000001],B[2000001],y,C[2000005];
int main()
{
f >> B;
f >> A;
m = strlen(B);
n = strlen(A);
strcpy(C,A);
strcpy(A+1,C);
strcpy(C,B);
strcpy(B+1,C);
p[1] = 0;
for(i = 2; i <= m ; i++){
q = p[i-1];
while ( B[i] != B[q+1] && q != 0 )
q = p[q];
if ( B[i] == B[q+1] )
p[i] = q + 1;
else
p[i] = 0;
}
q = 0;
for ( i = 1; i <= n ;i++){
while ( A[i] != B[q+1] && q!= 0 )
q = p[q];
if ( A[i] == B[q + 1] )
q++;
if( q == m ){
s[++nr] = i - m;
q = p[q];
}
}
g << nr << '\n';
if( nr > 1000)
nr = 1000;
for ( i = 1; i <= nr; i++)
g << s[i] << " ";
return 0;
}