Pagini recente » Cod sursa (job #2806283) | Cod sursa (job #2612537) | Cod sursa (job #544308) | Cod sursa (job #2515593) | Cod sursa (job #147503)
Cod sursa(job #147503)
#include <cstdio>
#include <cstring>
const long MAX = 2000010; // TODO: fix
char A[MAX], B[MAX];
long n,m;
long pi[MAX],i,k;
long nr, Store[1000];
int main() {
freopen("strmatch.in", "r", stdin);
scanf("%s\n%s\n", A+1, B+1);
n = strlen(A+1);
m = strlen(B+1);
pi[1] = 0; k = 0;
for (i=2; i<=n; ++i) {
while ( k>0 && A[i]!=A[k+1] ) k = pi[k];
if ( A[i]==A[k+1] ) ++k;
pi[i] = k;
}
k = 0;
for (i=1; i<=m; ++i) {
while ( A[k+1]!=B[i] && k>0 ) k = pi[k];
if ( A[k+1]==B[i] )
++k;
if ( k==n ) {
++ nr;
if ( Store[0]<1000 )
Store[++Store[0]] = i-n;
}
}
freopen("strmatch.out", "w", stdout);
printf("%ld\n", nr);
for (i=1; i<=Store[0]; ++i)
printf("%ld ", Store[i]);
return 0;
}