Cod sursa(job #934620)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 30 martie 2013 21:26:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#include <string>

#define MAX 2000005

using namespace std;

int N, M, cnt, prefix[MAX];
string A, B;
vector<int> ans;

void citire() {
    ifstream in("strmatch.in");
    in>>A>>B; in.close();
    N = A.length(), M = B.length();
    A = " " + A; B = " " + B;
}

void preprocess() {
    prefix[1] = 0;
    for(int i = 2, P = 0; i <= N; i++) {
        while(P && A[P + 1] != A[i]) P = prefix[P];
        if(A[P + 1] == A[i]) P++;
        prefix[i] = P;
    }
}

void solve() {
    preprocess();
    for(int i = 1, P = 0; i <= M; i++) {
        while(P && B[i] != A[P + 1]) P = prefix[P];
        if(B[i] == A[P + 1]) P++;
        if(P == N) {
            cnt++;
            if(ans.size() < 1000) ans.push_back(i - N);
            P = prefix[P];
        }
    }
}

void afisare() {
    ofstream out("strmatch.out");
    out<<cnt<<"\n";
    for(size_t i = 0; i < ans.size(); i++) out<<ans[i]<<" ";
    out.close();
}

int main() {
    citire();
    solve();
    afisare();
    return 0;
}