Pagini recente » Cod sursa (job #2378920) | Cod sursa (job #768146) | Cod sursa (job #1400995) | Cod sursa (job #1117723) | Cod sursa (job #1106270)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
int urm[2000002],q,v[2000002],i,n,m;
char s1[2000002],s2[2000002],s3[2000002]=" ";
void urmator(char s1[2000002])
{
int k,i;
k=0;
for(i=2;i<=m;i++)
{
while(k>0 && s1[i]!=s1[k+1])k=urm[k];
if(s1[k+1]==s1[i]) k++;
urm[i]=k;
}
}
int main()
{
fgets(s1,2000000,f);
strcpy(s1+strlen(s1)-1,s1+strlen(s1));
m=strlen(s1);
strcat(s3,s1);
strcpy(s1,s3);
fgets(s2,2000000,f);
strcpy(s2+strlen(s2)-1,s1+strlen(s2));
n=strlen(s2);
strcpy(s3," ");
strcat(s3,s2);
strcpy(s2,s3);
urmator(s1);
q=0;
for(i=1;i<=n;i++)
{
while(q>0 && s1[q+1]!=s2[i])q=urm[q];
if(s1[q+1]==s2[i]) q++;
if(q==m)
{
v[++v[0]]=i-m;
}
}
fprintf(g,"%d\n",v[0]);
for(i=1;i<=min(v[0],1000);i++)
fprintf(g,"%d ",v[i]);
fclose(g);
return 0;
}