Pagini recente » Cod sursa (job #1611784) | Cod sursa (job #1998111) | Cod sursa (job #2371806) | Cod sursa (job #2350249) | Cod sursa (job #1846731)
#include <stdio.h>
#include <fstream>
#include <cstring>
using namespace std;
char s1[2000000],s2[2000000];
int n,m,i,j,k;
int pi[2000001],sol[1001];
int main()
{
freopen("strmatch.in","r",stdin);
fstream out("strmatch.out");
scanf("%s",&s1);
scanf("%s",&s2);
n = strlen(s1);
m = strlen(s2);
for(i=1; i<n; i++)
{
while(k>0 && s1[i]!=s1[k])
k=pi[k-1];
if(s1[i]==s1[k])
k++;
pi[i]=k;
}
k=0;
for(i=0; i<m; i++)
{
while(k>0 && s2[i]!=s1[k])
k=pi[k-1];
if(s2[i]==s1[k])
k++;
if(k==n){
k = pi[n-1];
sol[++j] = i-n+1;
}
}
out<<j<<"\n";
j=(j<1000)?j:1000;
for(i=1;i<=j;i++)
out<<sol[i]<<" ";
return 0;
}