Cod sursa(job #249776)

Utilizator vlad_popaVlad Popa vlad_popa Data 29 ianuarie 2009 11:03:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAXN 2000015

int N, M;
char sir[MAXN], match[MAXN];
int p[MAXN];
vector <int> sol;

void read () {
    fgets (match, MAXN, stdin);
    fgets (sir, MAXN, stdin);
    N = strlen(sir) - 1; M = strlen(match) - 1;
}

#define sir (sir - 1)
#define match (match - 1)

void prefix () {
    int k = 0;
    for (int i = 2; i <= M; ++ i) {
        while (k > 0 && match[k + 1] != match[i]) k = p[k];
        if (match[k + 1] == match[i]) ++ k;
        
        p[i] = k;
    }
}

void KMP () {
    int k = 0;
    
    for (int i = 1; i <= N; ++ i) {
        while (k > 0 && match[k + 1] != sir[i]) k = p[k];
        if (match[k + 1] == sir[i]) ++ k;
        
        if (k == M) sol.push_back(i - M);
    }
}

void solve () {
    prefix ();
    KMP ();
    
    int sz = sol.size();
    printf ("%d\n", sz);
    for (int i = 0; i < sz; ++ i) printf ("%d ", sol[i]);
    printf ("\n");
}

int main () {
    freopen ("strmatch.in", "r", stdin);
    freopen ("strmatch.out", "w",stdout);
    
    read ();
    solve ();
    
    return 0;
}