Cod sursa(job #249796)

Utilizator vlad_popaVlad Popa vlad_popa Data 29 ianuarie 2009 11:31:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <vector>

using namespace std;

#define MAXN 2000015

int N, M;
char sir[MAXN], match[MAXN];
int p[MAXN];
int sol[1024], sz;

void read () {
    fgets (match, MAXN, stdin);
    fgets (sir, MAXN, stdin);
    for (; (match[M] >= 'A' && match[M] <= 'Z') || (match[M] >= 'a' && match[M] <= 'z')   
          || (match[M] >= '0' && match[M] <= '9'); ++M);  
    for (; (sir[N] >= 'A' && sir[N] <= 'Z') || (sir[N] >= 'a' && sir[N] <= 'z')  
          || (sir[N] >= '0' && sir[N] <= '9'); ++N);  
}

#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) {
            ++ sz;
            if (sz <= 1000)
                sol[sz] = i - M;
        }
    }
}

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

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