Pagini recente » Cod sursa (job #3278225) | Cod sursa (job #31178) | Cod sursa (job #1613353) | Cod sursa (job #2738319) | Cod sursa (job #947205)
Cod sursa(job #947205)
#include<cstdio>
#include<cstring>
using namespace std;
int i,poz[1002],phi[2000004],n,m,nr;
char a[2000004],b[2000004];
int min(int x,int y)
{
if (x>y) return y;
else return x;
}
void prefix()
{
int i,k;
phi[1]=0;
k=0;
for (i=2;i<=m;i++)
{
while(k!=0&&b[i]!=b[k+1])
k=phi[k];
if (b[i]==b[k+1])
k++;
phi[i]=k;
}
}
void kmpp()
{
int k,i;
k=0;
nr=0;
for (i=1;i<=n;i++)
{
while(k!=0&&a[i]!=b[k+1])
k=phi[k];
if (a[i]==b[k+1])
k++;
if (k==m)
{
nr++;
if (nr<=1000)
{
poz[nr]=i-k;
k=phi[k];
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(b+1);
gets(a+1);
m=strlen(b+1);
n=strlen(a+1);
prefix();
kmpp();
printf("%d\n",nr);
for (i=1;i<=min(1000,nr);i++)
{
printf("%d ",poz[i]);
}
printf("\n");
return 0;
}