Pagini recente » Cod sursa (job #913552) | Cod sursa (job #1479283) | Cod sursa (job #409609) | Cod sursa (job #2455172) | Cod sursa (job #1830962)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
char a[2000002],b[2000002];
int p[2000002],n,m;
int strlen(char *s)
{
int i;
for(i=0;s[i]!='\0';i++);
return i;
}
void sir_prefixe()
{
int i=2,j=1;
while(i<=n)
{
if(a[i]==a[j])
{
p[i]=j;
i++;
j++;
}
else
{
if(j>1)
j=p[j-1]+1;
else
{
p[i]=0;
i++;
j=1;
}
}
}
}
void kmp()
{
vector<int>q;
for(int j=1,i=0;j<=m;j++)
{
while(i>0 && b[j]!=a[i+1])
i=p[i];
if(b[j]==a[i+1])
i++;
if(i==n)
q.push_back(j-n);
}
int k = q.size();
printf("%d\n",k);
for(int i=0;i<k && i< 1000;i++)
printf("%d ",q[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",a+1,b+1);
n=strlen(a+1);
m=strlen(b+1);
sir_prefixe();
kmp();
return 0;
}