Cod sursa(job #880618)

Utilizator vendettaSalajan Razvan vendetta Data 16 februarie 2013 23:20:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 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 1005
#define ll long long
#define Sirmax 2000005

string A, B;
int rez[Sirmax], pi[Sirmax];

void citeste(){
    getline(f,A);
    getline(f,B);
    // le reindexez de la 1
    A += '#'; B += '#';
    for(int i=A.size()-1; i>=1; --i) A[i] = A[i-1];
    for(int i=B.size()-1; i>=1; --i) B[i] = B[i-1];
}

void prefix(){
    for(int i=2, q=0; i<A.size(); ++i){
        while( q>0 && A[q+1] != A[i]) q = pi[q];// ideea ar fi ca acum tot tai din prefixe
        // cand ma opresc insemana ca cel mai lung prefix care e sufix are lungimea q
        // incerc sa il fac de lungime q+1;
        if (A[q+1] == A[i]) ++q;
        pi[i] = q;
    }
}

void rezolva(){
    // imi fac functia prefix care o sa imi zice pentru sirul pi[i] = cel mai lung prefix 1...i care e sufix a acestei secvente
    prefix();
    //acum vad aparitiile
    int sz=0;

    for(int i=1,q=0; i<B.size(); ++i){
        while(q>0 && A[q+1] != B[i]) q = pi[q];// tot incerc urmatoarele potriviri
        if (A[q+1] == B[i]) q++;
        if (q == A.size() - 1){
            q = pi[q];
            rez[++sz] = i- (A.size()-1);// is indexate de la 0 (cere in enut)
        }
    }

    g << sz << "\n";
    //cout << sz << "\n";
    for(int i=1; i<=min(sz, 1000); ++i){
        //cout << rez[i]<< "\n";
        g << rez[i]<< " ";
    }
}

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

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

    return 0;
}