Cod sursa(job #970222)

Utilizator Theorytheo .c Theory Data 6 iulie 2013 11:30:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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


const int Nmax = 2000009;

int N; int M; char A[Nmax]; char B[Nmax]; int H[Nmax]; int q = 0;

vector <int> V;

void Read() {

    fin >> A + 1; fin.get();
    fin >> B + 1;
    N = strlen(A + 1);
    M = strlen(B + 1);
}

void Precalc() {

    for(int i = 2; i <= N; ++i) {

        while(q > 0 && A[i] != A[q + 1])
            q = H[q];

        if(A[i] == A[q + 1])   ++q;

        H[i] = q;
    }
}

void Solve() {

    q = 0;

    for(int i = 1; i <= M; ++i) {

        while(q && B[i] != A[q + 1])
            q = H[q];
        if(A[q + 1] == B[i]) ++q;

        if(q == N) V.push_back(i - q);
    }
}

void Print() {

    fout << V.size() <<'\n';

    for(int i = 0 ; i < V.size(); ++i)
        fout << V[i] << " ";
}

int main() {

    Read();

    Precalc(); Solve (); Print ();

    return 0;
}