Cod sursa(job #899996)

Utilizator vendettaSalajan Razvan vendetta Data 28 februarie 2013 17:15:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 2000005
#define ll long long

string P, T;
int pi[nmax], Pn, Tn, rez[1005];

void citeste(){
    getline(f, P);
    getline(f, T);
    // le reindexez;
    P += '#'; T += '#';
    for(int i=P.size()-1; i>=1; --i) P[i] = P[i-1];
    for(int i=T.size()-1; i>=1; --i) T[i] = T[i-1];
    Pn = P.size()-1; Tn = T.size()-1;
}

void prefix(){
    pi[1] = 0;
    for(int i=2, q=0; i<=Pn; ++i){
        while(q>0 && P[q+1] != P[i]) q=pi[q];
        if (P[q+1] == P[i]) ++q;
        pi[i] = q;
    }
}

void bagaKmp(){
    for(int i=1, q=0; i<=Tn; ++i){
        while( q>0 && P[q+1] != T[i]) q= pi[q];
        if (P[q+1] == T[i]) ++q;
        if (q == Pn){// am gasit o aparitie
            ++rez[0];
            if (rez[0] <= 1000) rez[rez[0]] = i-Pn;
        }
    }
}

void rezolva(){
    prefix();
    bagaKmp();
    g << rez[0] << "\n";
    rez[0] = min(rez[0], 1000);
    for(int i=1; i<=rez[0]; ++i) g << rez[i] << " ";
    g << "\n";
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}