Pagini recente » Cod sursa (job #2500908) | Cod sursa (job #1601781) | Cod sursa (job #1151758) | Cod sursa (job #285668) | Cod sursa (job #1659752)
#include <stdio.h>
#include <string.h>
#define mx 2000010
using namespace std;
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
long pi[mx+1],v[1024],i,h,n,m,p;
char s1[mx+2],s2[mx+2];
void prefix()
{
p=0;pi[0]=0;
for (i=2;i<=n;i++)
{
while (p>0&&s1[i]!=s1[p+1])
p=pi[p];
if (s1[i]==s1[p+1])
p++;
pi[i]=p;
}
}
void kmp()
{
p=0;
h=0;
for (i=1;i<=m;i++)
{
while (p>0&&s2[i]!=s1[p+1])
p=pi[p];
if (s2[i]==s1[p+1]) p++;
if (p==n)
{
p=pi[p];
h++;
if (h<=1000)
v[h]=i-n;
}
}
}
int main()
{
fgets(s1+1,mx,f);
fgets(s2+1,mx,f);
n=strlen(s1+1)-1;
m=strlen(s2+1)-1;
prefix();
kmp();
fprintf(g,"%ld\n",h);
if (h>1000) h=1000;
for (i=1;i<=h;i++) fprintf(g,"%ld ",v[i]);
fclose(g);
fclose(f);
return 0;
}