Pagini recente » Cod sursa (job #2136504) | Cod sursa (job #1520209) | Cod sursa (job #1115020) | Cod sursa (job #24719) | Cod sursa (job #291458)
Cod sursa(job #291458)
#include<stdio.h>
#include<string.h>
#define Q 2000001
char A[Q],B[Q];
int k,n,m,v[1001],num,pi[Q];
void p()
{
pi[1]=0;
k=0;
for (int i=2; i<=n; ++i)
{
while (k&&A[k+1]!=A[i])
k=pi[k];
if (A[k+1]==A[i])
++k;
pi[i]=k;
}
}
void kmp()
{
k=0;
for (int i=1; i<=m; ++i)
{
while (k&&A[k+1]!=B[i])
k=pi[k];
if (A[k+1]==B[i])
++k;
if (k==n)
{
v[++num]=i-n;
k=pi[n];
}
}
}
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A,sizeof(A),stdin);
fgets(B,sizeof(B),stdin);
for (; A[n]; ++n);--n;
for (;B[m]; ++m);--m;
for (int i=n; i; --i) A[i]=A[i-1];
A[0]=' ';
for (int i=m; i; --i) B[i]=B[i-1];
B[0]=' ';
p();
kmp();
printf("%d\n",num);
for (int i=1; i<=num && i<=1000; ++i)
printf("%d ",v[i]);
}
int main()
{
citire();
return 0;
}