Cod sursa(job #1574438)

Utilizator TonyFrumTony Frum TonyFrum Data 20 ianuarie 2016 16:29:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int MAX_LEN = 2000000;

char W[5 + MAX_LEN];
char S[5 + MAX_LEN];
int pi[5 + MAX_LEN];

int main() {
    int i, q, n, m;
    vector < int > sol;

    in >> W + 1;
    in >> S + 1;

    n = strlen(W + 1);
    m = strlen(S + 1);

    for(i = 2, q = 0, pi[1] = 0; i <= m; i++) {
        while(q > 0 && W[q + 1] != W[i]) q = pi[q];
        if(W[q + 1] == W[i]) q++;
        pi[i] = q;
    }

    for(i = 1, q = 0; i <= m; i++) {
        while(q > 0 && W[q + 1] != S[i]) q = pi[q];
        if(W[q + 1] == S[i]) q++;
        if(q == n) sol.push_back(i - n);
    }

    out << sol.size() << '\n';
    for(i = 0; i < min(sol.size(), 1000u); i++) out << sol[i] << ' ';

    return 0;
}