Cod sursa(job #668749)

Utilizator deneoAdrian Craciun deneo Data 25 ianuarie 2012 16:10:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

char a[2000001], b[2000001];
int n, m, pi[2000001], p = 0, sp[2001];

void make_prefix() {
    int i, k = 0;
    for(i = 2; i <= n; ++i) {
        while(k > 0 && a[k + 1] != a[i])
            k = pi[k];
        if(a[k + 1] == a[i])
            ++k;
        pi[i] = k;
    }

}

int main() {
    int i, k = 0;
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(a + 1, 2000001);
    f.getline(b + 1, 2000001);

    n = strlen(a + 1); m = strlen(b + 1);
    make_prefix();

    for(i = 1; i <= m; ++i) {
        while(k > 0 && a[k + 1] != b[i])
            k = pi[k];
        if(a[k + 1] == b[i])
            ++k;
        if(k == n) {
            k = pi[k];
            ++p;
            if(p <= 1000) sp[p] = (i - n);
        }
    }

    g << p << '\n';
    for(i = 1; i <= min(p, 1000); ++i)
        g << sp[i] << ' ';
    g.close();
    return 0;
}