Pagini recente » Cod sursa (job #782464) | Cod sursa (job #37197) | Cod sursa (job #1382036) | Cod sursa (job #1009413) | Cod sursa (job #1106227)
#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[2000000],q,v[2000000],i,n,m;
char s1[2000000],s2[2000000];
void urmator(char s1[2000000])
{
int k,i;
k=-1;
for(i=2;i<=m;i++)
{
while(k>0 && s1[i-1]!=s1[k+1])k=urm[k];
if(s1[k+1]==s1[i-1]) k++;
urm[i]=k+1;
}
}
int main()
{
fgets(s1,2000000,f);
strcpy(s1+strlen(s1)-1,s1+strlen(s1));
m=strlen(s1);
fgets(s2,2000000,f);
strcpy(s2+strlen(s2)-1,s1+strlen(s2));
urmator(s1);
n=strlen(s2);
q=-1;
for(i=1;i<=n;i++)
{
while(q>0 && s1[q+1]!=s2[i-1])q=urm[q+1]-1;
if(s1[q+1]==s2[i-1]) q++;
if(q==m-1)
{
v[++v[0]]=i-m;
}
}
fprintf(g,"%d\n",v[0]);
for(i=1;i<=max(v[0],1000);i++)
fprintf(g,"%d ",v[i]);
return 0;
}