Cod sursa(job #2281501)

Utilizator waren4Marius Radu waren4 Data 12 noiembrie 2018 12:59:41
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in"); ofstream g("strmatch.out");

string a,b,s; int nr, alen, blen; int p[2000005]; int sol[2000005];

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

int main() {
    int i, q;
    a += ' ';
    b += ' ';
    f>>s;
    a += s;
    f>>s;
    b += s;

    alen = a.length();
    blen = b.length();

    prefix();

    q = 0; nr = 0; --alen;
    for(i = 1; i < blen; ++i) {
        while((q > 0) && (b[i] != a[q + 1])) {
            q = p[q];
        }
        if(b[i] == a[q + 1]) {
            ++q;
        }
        if(q == alen) {
            ++nr;
            sol[nr] = i - alen;
        }
    }
    g<<nr<<'\n';
    for(i = 1; i <= nr; ++i) {
        g<<sol[i]<<' ';
    }
    return 0;
}