Cod sursa(job #598844)

Utilizator cosmyoPaunel Cosmin cosmyo Data 27 iunie 2011 13:21:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2000005;
char t[N], p[N];
int L[N], n, m, sol[1005], nr;

inline void prefix() {
    int i, k = 0, n = strlen(p);
    L[1] = 0;
    for(i = 2; i <= n; ++i) {
        k = L[i - 1];
        while(k && p[k] != p[i - 1])
            k = L[k];

        if(p[k] == p[i - 1])
            ++k;
        L[i] = k;
    }
}

inline void kmp() {
    int i, k, n = strlen(t);
    k = 0;
    for(i = 1; i <= n; ++i){
        while(k > 0 && p[k] != t[i - 1])
            k = L[k];
        if(p[k] == t[i - 1])
            ++k;
        if(k == m){
            if(nr < 1000)
                sol[++nr] = i - m ;
            k = L[k];
        }
    }
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int i, j;
    scanf("%s\n %s", &p, &t);
    m = strlen(p);
    n = strlen(t) - 1;
    prefix();
    kmp();
    printf("%d\n", nr);
    for(i = 1; i <= nr; ++i)
        printf("%d ", sol[i]);
    printf("\n");
    return 0;
}