Pagini recente » Cod sursa (job #685196) | Cod sursa (job #2577037) | Cod sursa (job #2197553) | Cod sursa (job #1587597) | Cod sursa (job #1659740)
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,pi[2000010],v[1001],h;
char s1[2000010],s2[2000010];
void prefix()
{
int p=0;
for(int i=2;i<=n;i++)
{
while(p&&s1[i]!=s1[p+1])p=pi[p];
if(s1[i]==s1[p+1])p++;
pi[i]=p;
}
}
void kmp()
{
int p=0;
prefix();
for(int i=1;i<=m;i++)
{
while(p&&s2[i]!=s1[p+1])p=pi[p];
if(s2[i]==s1[p+1])p++;
if(p==n)if(++h<=1000)v[h]=i-n;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1+1,2000010,stdin);
fgets(s2+1,2000010,stdin);
n=strlen(s1+1)-1;
m=strlen(s2+1)-1;
kmp();
printf("%d\n",h);
if(h>1000)h=1000;
for(int i=1;i<=h;i++)
printf("%d ",v[i]);
fclose(stdin);
fclose(stdout);
return 0;
}