Pagini recente » Cod sursa (job #2759853) | Cod sursa (job #757570) | Cod sursa (job #1594805) | Cod sursa (job #604625) | Cod sursa (job #922446)
Cod sursa(job #922446)
#include <iostream>
#include <cstdio>
#include <cstring>
#define DN 2000005
using namespace std;
char a[DN],b[DN];
int pi[DN],poz[1005];
void prefix()
{
int k=0 , n=strlen(a+1);
pi[1]=0;
for(int i=2;i<=n;++i)
{
while(k>0 && a[k+1]!=a[i])
k=pi[k];
if(a[i]==a[k+1])
++k;
pi[i]=k;
}
}
int main()
{
freopen("strmatch.in","r", stdin);
freopen("strmatch.out","w", stdout);
scanf("%s\n",a+1);
scanf("%s",b+1);
prefix();
int q=0 , m=strlen(b+1) , n=strlen(a+1),rest=0;
for(int i=1;i<=m;++i)
{
while(q>0 && a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(n==q)
{
q=pi[q];
if(poz[0]<1000)
poz[++poz[0]]=i-n;
else
++rest;
}
}
printf("%d\n",poz[0]+rest);
for(int i=1;i<=poz[0];++i)
printf("%d ",poz[i]);
return 0;
}