Pagini recente » Cod sursa (job #3032064) | Monitorul de evaluare | Profil cristianXIII | Cod sursa (job #2078056) | Cod sursa (job #578138)
Cod sursa(job #578138)
#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)-1;
long i,k;
l[0]=0;
for(i=1;i<=ls;++i)
{
k=l[i-1];
while(k>0 && s[k]!=s[i])
k=l[k-1];
if(s[k]==s[i])
++k;
l[i]=k;
}
}
void kmp()
{
lt=strlen(t)-1;
long i,k;
k=0;
for(i=0;i<=lt;++i)
{
while(k>0 && s[k]!=t[i])
k=l[k-1];
if(s[k]==t[i])
++k;
if(k==ls)
{
nr++;
if(nr<=1000)
poz[nr]=i-k+1;
k=l[k-1];
}
}
}
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;
}