Cod sursa(job #1944066)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 28 martie 2017 22:24:05
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char a[2000002], b[2000002];
int i, q, lung[2000002], vs[1005], sol, n, m;

int main() {
    f >> a+1 >> b+1;
    n = strlen(a+1), m = strlen(b+1);
    for (i = 2; i <= n; i++) {
        while (a[q+1] != a[i] && q)
            q = lung[q];
        if (a[q+1] == a[i]) q++;
        lung[i] = q;
    }
    for (i = 1, q = 0; i <= m; i++) {
        while (a[q+1] != b[i] && q)
            q = lung[q];
        if (a[q+1] == b[i]) q++;
        if (q == n) {
            if (sol<=1000)
                vs[++sol] = i-q;
        }
    }
    g << sol << '\n';
    for (i = 1; i <= sol; i++)
        g << vs[i] << ' ';

    return 0;
}