Pagini recente » Cod sursa (job #2108063) | Cod sursa (job #1486006) | Cod sursa (job #2335843) | Cod sursa (job #2148648) | Cod sursa (job #1133108)
#include <iostream>
#include<stdio.h>
#include<cstdlib>
#include<string.h>
#include<math.h>
using namespace std;
FILE *f,*g;
int n,m,i,j,first,curr,val[2000000],l;
char a[2000000],b[2000000];
int kmp[2000000];
int main()
{
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fscanf(f,"%s%s",&a,&b);
n=strlen(a);
m=strlen(b);
kmp[0]=1;
if (n==1)
{
for(i=0;i<=m-1;i++)
{
if (a[0]==b[i])
{
l++;
val[l]=i;
}
}
fprintf(g,"%d\n",l);
for(i=1;i<=min(l,1000);i++) fprintf(g,"%d ",val[i]);
return 0;
}
for(i=1;i<=n-1;i++)
{
j=kmp[i-1];
while(j<i&&a[i]!=a[i-j])
j+=kmp[i-1-j];
if (j==i) {if (a[i]==a[0]) kmp[i]=i; else kmp[i]=i+1;}
else kmp[i]=j;
}
if (a[0]==b[0]) {first=0;}
else {first=1;}
for(i=1;i<=m-1;i++)
{
while(first<i&&b[i]!=a[i-first]) first+=kmp[i-1-first];
if (first==i) {if (b[i]==a[0]) first=i; else first=i+1;}
if (i-first==n-1)
{l++;val[l]=first;
first+=kmp[n-1];
}
}
fprintf(g,"%d\n",l);
for(i=1;i<=min(l,1000);i++) fprintf(g,"%d ",val[i]);
return 0;
}