Pagini recente » Cod sursa (job #1624396) | Cod sursa (job #1959637) | Cod sursa (job #658099) | Cod sursa (job #1073727) | Cod sursa (job #1106224)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
FILE *f=fopen("kmp.in","r");
FILE *g=fopen("kmp.out","w");
int urm[2000000],q,v[2000000],i,n,m;
char s1[2000000],s2[2000000];
void urmator(char s1[2000000])
{
int k,i;
k=-1;
for(i=2;i<=m;i++)
{
while(k>0 && s1[i-1]!=s1[k+1])k=urm[k];
if(s1[k+1]==s1[i-1]) k++;
urm[i]=k+1;
}
}
int main()
{
fgets(s1,2000000,f);
strcpy(s1+strlen(s1)-1,s1+strlen(s1));
m=strlen(s1);
fgets(s2,2000000,f);
strcpy(s2+strlen(s2)-1,s1+strlen(s2));
urmator(s1);
n=strlen(s2);
q=-1;
for(i=1;i<=n;i++)
{
while(q>0 && s1[q+1]!=s2[i-1])q=urm[q+1]-1;
if(s1[q+1]==s2[i-1]) q++;
if(q==m-1)
{
v[++v[0]]=i-m;
}
}
fprintf(g,"%d\n",v[0]);
for(i=1;i<=v[0];i++)
fprintf(g,"%d ",v[i]);
return 0;
}