Pagini recente » Cod sursa (job #1255948) | Cod sursa (job #181214) | Cod sursa (job #2618829) | Cod sursa (job #3167466) | Cod sursa (job #169744)
Cod sursa(job #169744)
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("strmatch.in","r");
FILE*fout=fopen("strmatch.out","w");
#define maxn 2000001
int nrp=0,n,m,p[1001],sup[maxn];
char s[maxn],t[maxn];
void prefix()
{
int k=0,i;
sup[1]=0;
for(i=2;i<=m;i++)
{
while(k>0&&s[k]!=s[i-1]) k=sup[k];
if(s[k]==s[i-1]) k++;
sup[i]=k;
}
}
void kmp()
{
int k=0,i;
for(i=1;i<=n;i++)
{
while(k>0&&s[k]!=t[i-1]) k=sup[k];
if(s[k]==t[i-1]) k++;
if(k==m)
{
nrp++;
if(nrp<=1000) p[nrp]=i-m;
k=sup[k];
}
}
}
int main()
{
int i;
fscanf(fin,"%s",&s);
fscanf(fin,"%s",&t);
n=strlen(t);
m=strlen(s);
nrp=0;
fclose(fin);
prefix();
kmp();
fprintf(fout,"%d\n",nrp);
if(nrp>1000) nrp=1000;
for(i=1;i<=nrp;i++)
fprintf(fout,"%d%c",p[i],' ');
fclose(fout);
return 0;
}