Cod sursa(job #1161809)

Utilizator SRaduRadu Szasz SRadu Data 31 martie 2014 14:28:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;

const int MAX = 2000050;

char A[MAX], B[MAX];
int ans, pfix[MAX];

vector<int> V;

void citire() {
    ifstream in("strmatch.in");
    in.getline(A + 1, MAX);
    in.getline(B + 1, MAX);
    in.close();
}

void kmp() {
    int N = strlen(A + 1), M = strlen(B + 1);
    pfix[1] = 0;
    for(int i = 2, poz = 0; i <= N; i++) {
        while(poz && A[poz + 1] != A[i]) 
            poz = pfix[poz];
        if(A[poz + 1] == A[i]) poz++;
        pfix[i] = poz;
    }
    for(int i = 1, poz = 0; i <= M; i++) {
        while(poz && A[poz + 1] != B[i])
            poz = pfix[poz];
        if(A[poz + 1] == B[i])
            poz++;
        if(poz == N) {
            ans++;
            if(V.size() < 1000)
                V.push_back(i - N);
            poz = pfix[poz];
        }
    }
}

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

int main() {
    citire();
    kmp();
    afisare();
}