Pagini recente » Cod sursa (job #730192) | Cod sursa (job #2142989) | Cod sursa (job #2018402) | Cod sursa (job #2202776) | Cod sursa (job #1638879)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int sol[1010],pi[2000010];
char sir1[2000010],sir2[2000010];
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),nr=0;
for(int i=2,k=0;i<=n;i++)
{
while(k && sir1[k+1]!=sir1[i]) k=pi[k];
if(sir1[k+1]==sir1[i]) k++;
pi[i]=k;
}
for(int i=1,k=1;i<=m;i++)
{
while(k && sir1[k+1]!=sir2[i]) k=pi[k];
if(sir1[k+1]==sir2[i]) k++;
if(k==n)
{
nr++;
if(nr<=1000) sol[nr]=i-n;
k=pi[k];
}
}
printf("%d\n",nr);
nr=min(nr,1000);
for(int i=1;i<=nr;i++) printf("%d ",sol[i]);
return 0;
}