Cod sursa(job #796627)

Utilizator tsubyRazvan Idomir tsuby Data 11 octombrie 2012 22:33:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <cstring>
#define minim(a,b)((a < b) ? a:b)
#define N 20000001

char a[N], b[N];
int m, n, nr, pi[N], q = 0, pos[1024];

void prefix(){
    pi[1] = 0;
    for(int i=2;i<=n;i++)
    {
        while(q>0 && a[q+1] != a[i])
            q = pi[q];
        if(a[q+1] == a[i])
            q++;
        pi[i] = q;
    }
}
void kmp()
{
    n=strlen(a),m=strlen(b);
    for (int i = n; i; i--)
        a[i] = a[i-1];
    a[0] = ' ';
    for (int i = m; i; i--)
        b[i] = b[i-1];
    b[0] = ' ';

    prefix();

    for(int i=0;i<=m;i++)
    {
        while(q>0 && a[q+1]!= b[i])
            q = pi[q];
        if(a[q+1] == b[i])
            q++;
        if(q == n)
        {
            q = pi[n];
            nr++;
            if(nr<=1000)
                pos[nr] = i-n;
        }
    }

    printf("%d\n", nr);
    for(int i = 1; i <= minim(nr,1000); i++)
        printf("%d ",pos[i]);
    printf("\n");
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s", a, b);
    kmp();

    return 0;
}