Pagini recente » Cod sursa (job #73524) | Cod sursa (job #1264984) | Cod sursa (job #1191844) | Cod sursa (job #2152644) | Cod sursa (job #298370)
Cod sursa(job #298370)
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("kmp.in","r");
FILE*fout=fopen("kmp.out","w");
#define nm 2000005
char s[nm],t[nm];
int sup[nm],dim=0,p[nm],n,m;
void prefix()
{
int k=0,i;
sup[0]=0;
for(i=1;i<m;i++)
{
while(k&&s[k]!=s[i]) k=sup[k-1];
if(s[k]==s[i]) k++;
sup[i]=k;
}
}
void kmp()
{
int k=0,i;
for(i=0;i<n;i++)
{
while(k&&s[k]!=t[i]) k=sup[k-1];
if(s[k]==t[i]) k++;
if(k==m)
{
dim++;
p[dim]=i-m+1;
k=sup[k-1];
}
}
}
int main()
{
fscanf(fin,"%s",&s);
fscanf(fin,"%s",&t);
m=strlen(s);
n=strlen(t);
prefix();
kmp();
fprintf(fout,"%d\n",dim);
if(dim>1000) dim=1000;
for(int i=1;i<=dim;i++)
fprintf(fout,"%d ",p[i]);
fclose(fin);
fclose(fout);
return 0;
}