Pagini recente » Cod sursa (job #2354366) | Cod sursa (job #1732234) | Cod sursa (job #2926748) | Cod sursa (job #1196840) | Cod sursa (job #1106271)
#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[1005],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=0;
for(i=2;i<=n;i++)
{
while(k>0 && s[k]!=s[i-1])k=urm[k];
if (s[k]==s[i-1])k++;
urm[i]=k;
}
//for(i=1;i<n;i++)
//urm[i]=urm[i]+1;
q=0;
for(i=0;i<m;i++)
{
while (q>0 && s[q]!=ss[i])q=urm[q];
if (s[q]==ss[i])q++;
if (q==n){if (nr<1000)r[++nr]=i-n+1;else nr++;}
}
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;
}