Cod sursa(job #1659746)

Utilizator NightSilentIridon Stefan NightSilent Data 22 martie 2016 16:05:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define mx 2000010
using namespace std;
long i,h,n,m,p;
long pi[mx+1];
long v[1024];
char s1[mx+2],s2[mx+2];
void prefix()
{
    int i;
    pi[0]=0;
    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()
{
    n=strlen(s1+1)-1;
    m=strlen (s2+1)-1;
    prefix();
    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)
        {
            h++;
            p=pi[p];
            if (h<=1000)
                v[h]=i-n;
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(s1+1,mx,stdin);
    fgets(s2+1,mx,stdin);
    kmp();
    printf("%ld\n",h);
    if (h>1000)
        h=1000;
    for (i=1;i<=h;i++)
        printf("%ld ",v[i]);
    return 0;
}