Pagini recente » Cod sursa (job #353028) | Cod sursa (job #1039259) | Cod sursa (job #290736) | Cod sursa (job #1689717) | Cod sursa (job #552372)
Cod sursa(job #552372)
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000001];
char b[2000001];
int nr,k[1001],nr1;
int v[2000001];
int n,m;
void kmp()
{
int i=0;
int j=-1;
v[i]=j;
while (i<n)
{
while(j>=0 && a[j]!=a[i])
j=v[j];
i++;
j++;
v[i]=j;
}
}
void cauta()
{
int i=0;
int j=0;
// v[i]=j;
while (i<m)
{
while (j>=0 && b[i]!=a[j])
j=v[j];
j++;
i++;
if (j==n)
{
if (nr1<1000)
k[nr1]=i-j;
nr1++;
j=v[j];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
n=strlen(a);
m=strlen(b);
kmp();
cauta();
printf("%d\n",nr1);
if(nr1>1000)
nr1=1000;
for (int i=0;i<nr1;i++)
printf("%d ",k[i]);
return 0;
}