Cod sursa(job #434049)

Utilizator Omega91Nicodei Eduard Omega91 Data 4 aprilie 2010 22:55:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <iostream>
using namespace std;

const int NMAX = 2000001;

void fail_func(char w[], int T[])
{
    T[0] = -1;
    int i = 1, j = 0;
    for(; w[i]; ++i)
        if (w[i] == w[j])
            T[i] = T[j++];
        else {
            T[i] = j;
            j = 0;
        }
    T[i] = j;
}

int kmp(char S[], char W[], int T[], int& i)
{
    static int j = 0;
    for (; S[i]; ) {
        if (S[i] == W[j]) {
            ++i, ++j;
            if (!W[j]) {
                int x = i - j;
                j = T[j];
                return x;
            }
        }
        else if (T[j] == -1)
            ++i, j = 0;
        else
            j = T[j];
    }
    return -1;
}

char S[NMAX] = {}, W[NMAX] = {};

int main()
{
    int *t, i = 0;
    int ans[1001] = {}, k = 0;
    ifstream f1("strmatch.in");
    freopen("strmatch.out", "w", stdout);
    f1 >> W >> S;
    
    
    fail_func(W, t = new int [NMAX]);
    while( (ans[k] = kmp(S, W, t, i)) != -1 && ++k != 1000 );
    printf("%d\n", k);
    for (i = 0; i != k; ++i)
        printf("%d ", ans[i]);
    return 0;
}