Cod sursa(job #143836)

Utilizator damaDamaschin Mihai dama Data 26 februarie 2008 21:39:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <string.h>


const int nm = 1 << 21;

char a[nm], b[nm];
int pi[nm], sol[1024], cnt;

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    int i, s1, s2, k;

    fgets(a, nm, stdin);
    s1 = strlen(a) - 1;
    fgets(b, nm, stdin);
    s2 = strlen(b) - 1;

    pi[0] = -1;
    k = -1;

    for(i = 1; i < s1; ++i)
    {
        while(k != -1 && a[i] != a[k + 1])
        {
            k = pi[k];
        }
        if(a[i] == a[k + 1])
        {
            ++k;
        }
        pi[i] = k;
        //printf("%d %d\n", i, pi[i]);
    }

    k = -1;

    for(i = 0; i < s2; ++i)
    {
        //printf("%d\n", k);
        while(k != -1 && b[i] != a[k + 1])
        {
            k = pi[k];
        }
        if(b[i] == a[k + 1])
        {
            ++k;
        }
        if(k == s1 - 1)
        {
            ++cnt;
            if(cnt <= 1000)
                sol[cnt] = i - s1 + 1;
        }
    }

    printf("%d\n", cnt);

    if(cnt > 1000)
        cnt = 1000;
    for(i = 1; i <= cnt; ++i)
    {
        printf("%d ", sol[i]);
    }

    return 0;
}