Pagini recente » Cod sursa (job #2738589) | Cod sursa (job #812874) | Cod sursa (job #2662868) | Cod sursa (job #1423255) | Cod sursa (job #1106241)
#include <stdio.h>
#include <string.h>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
char s[2000002],ss[2000002];
int k,n,m,urm[2000002],i,q,r[2000002],nr;
int main()
{
fgets(s,2000002,f);
strcpy(s+strlen(s)-1,s+strlen(s));
fgets(ss,2000002,f);
strcpy(ss+strlen(ss)-1,ss+strlen(ss));
k=0;
n=strlen(s);
m=strlen(ss);
urm[0]=0;
k=-1;
for(i=1;i<n;i++)
{
while(k>0 && s[k]!=s[i])k=urm[i-1];
if (s[k+1]==s[i])k++;
urm[i]=k;
}
//for(i=1;i<n;i++)
//urm[i]=urm[i]+1;
q=-1;
for(i=0;i<m;i++)
{
while (q>-1 && s[q+1]!=ss[i])q=urm[q];
if (s[q+1]==ss[i])q++;
if (q==n-1)r[++nr]=i-n+1;
}
fprintf(g,"%d\n",nr);
if (nr>1000)nr=1000;
for(i=1;i<=nr;i++)
fprintf(g,"%d ",r[i]);
fclose(g);
return 0;
}