Pagini recente » Cod sursa (job #501075) | Cod sursa (job #935546) | Cod sursa (job #660084) | Cod sursa (job #1567564) | Cod sursa (job #1650709)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char sir1[2000010],sir2[2000010];
int d[2000010],sol[1010];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s",sir1+1,sir2+1);
int n=strlen(sir1+1),m=strlen(sir2+1),x=0,lim=0,nr=0;
for(int i=2;i<=n;i++)
{
if(i<=lim) d[i]=min(lim-i+1,d[i-x+1]);
while(i+d[i]<=n && sir1[d[i]+1]==sir1[i+d[i]]) d[i]++;
if(i+d[i]-1>lim) {lim=i+d[i]-1;x=i;}
}
x=0;lim=0;
for(int i=1;i<=m;i++)
{
int k=0;
if(i<=lim) k=min(lim-i+1,d[i-x+1]);
while(i+k<=m && k+1<=n && sir1[k+1]==sir2[i+k]) k++;
if(i+k-1>lim) {lim=i+k-1;x=i;}
if(k==n)
{
nr++;
if(nr<=1000) sol[nr]=i-1;
}
}
printf("%d\n",nr);
nr=min(nr,1000);
for(int i=1;i<=nr;i++) printf("%d ",sol[i]);
return 0;
}