Pagini recente » Cod sursa (job #2370506) | Cod sursa (job #2910246) | Cod sursa (job #2802660) | Cod sursa (job #2564017) | Cod sursa (job #2546518)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s1[2000001], s2[2000001];
int prefix[2000001], sol[2000001];
int main() {
FILE *fin, *fout;
int n, m, lc, i, nr;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
fscanf(fin, "%s\n%s",&s1,&s2);
n=strlen(s1);
m=strlen(s2);
prefix[0]=-1;
lc=-1;
for(i=1;i<n;i++) {
while(lc!=-1 && s1[i]!=s1[lc+1])
lc=prefix[lc];
if(s1[i]==s1[lc+1])
lc++;
prefix[i]=lc;
}
lc=-1;
nr=0;
for(i=0;i<m;i++) {
while(lc!=-1 && s2[i]!=s1[lc+1])
lc=prefix[lc];
if(s2[i]==s1[lc+1]) {
lc++;
if(lc==n-1)
sol[nr++]=i-n+1;
}
}
fprintf(fout, "%d\n",nr);
for(i=0;i<nr;i++)
fprintf(fout, "%d ",sol[i]);
return 0;
}