Pagini recente » Cod sursa (job #198547) | Cod sursa (job #2766925) | Cod sursa (job #1157967) | Cod sursa (job #1618080) | Cod sursa (job #1659749)
#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+10],s2[mx+10];
void prefix()
{
p=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();
if (h>1000) h=1000;
fprintf(g,"%ld\n",h);
for (i=1;i<=h;i++) fprintf(g,"%ld ",v[i]);
fclose(g);
fclose(f);
return 0;
}