Pagini recente » Cod sursa (job #1721472) | Cod sursa (job #1568454) | Cod sursa (job #2649747) | Cod sursa (job #559386) | Cod sursa (job #578137)
Cod sursa(job #578137)
#include<stdio.h>
#include<string.h>
#define M 2000003
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
char s[M], t[M];
long lt,ls,l[M];
long long nr=0;
long poz[1002];
void pref()
{
ls=strlen(s)-2;
long i,k;
l[1]=0;
for(i=2;i<=ls;++i)
{
k=l[i-1];
while(k>0 && s[k+1]!=s[i])
k=l[k];
if(s[k+1]==s[i])
++k;
l[i]=k;
}
}
void kmp()
{
lt=strlen(t)-2;
long i,k;
k=0;
for(i=1;i<=lt;++i)
{
while(k>0 && s[k+1]!=t[i])
k=l[k];
if(s[k+1]==t[i])
++k;
if(k==ls)
{
nr++;
if(nr<=1000)
poz[nr]=i-k;
k=l[k];
}
}
}
void afis()
{
long long max,i;
fprintf(g,"%lld\n",nr);
max=nr;
if(nr>1000) max=1000;
for(i=1;i<=max;++i)
fprintf(g,"%ld ",poz[i]);
}
int main()
{
char w[M];
fgets(s,M,f);
strcpy(w,s);
strcpy(s+1,w);
fgets(t,M,f);
strcpy(w,t);
strcpy(t+1,w);
pref();
kmp();
afis();
fclose(g);
fclose(f);
return 0;
}