Cod sursa(job #906557)

Utilizator vendettaSalajan Razvan vendetta Data 6 martie 2013 21:49:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 3.86 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 ll long long
#define nmax 2000005

string S, P, T;
int z[nmax*2];
int rez[1004];

void citeste(){
    getline(f, P);
    getline(f, T);
    S = P + T;
    S += '#'; for(int i=S.size()-1; i>=1; --i) S[i] = S[i-1];// l-am indexat de la 1
}

int compara(int x, int y, int &dr){
    int cnt = 0;
    for(int i=x, j=y; i<S.size(); ++i, ++j){
        if (S[i] != S[j]) break;
        ++cnt;
    }
    if (cnt != 0){// am gasit ceva
        dr = x + cnt - 1;
    }
    return cnt;
}

void Zvalues(){
    z[1] = S.size()-1;// dimensiunea stringului original e S.size()-1 pt ca am adaug caracaterul '#';
    int st = 1; int dr = 1;
    for(int i=2; i<S.size(); ++i){
        if (dr < i){
            z[i] = compara(i, 1, dr);// cat de mult ma pot duce in dreapta
            if (z[i] != 0) st = i;
            continue;
        }else {// dr >= i
            int Lung = dr - st + 1; int i1 = 1 + (dr-i+1) - 1;
            if (z[i1] < Lung){// se vede de ce pe foaie
                z[i] = z[i1];
            }
            if (z[i1] > Lung){// se vede de ce pe foaie
                z[i] = Lung;
            }
            if (z[i1] == Lung){
                int dr2 = 1 + Lung - 1;
                z[i] = z[i1] + compara(dr+1, dr2+1, dr);
                if (z[i] != z[i1])st = i;
            }
        }
    }
    /*
    for(int i=1; i<S.size(); ++i){
        cout << z[i] << " ";
    }
    cout << "\n";
    */
}

void rezolva(){
    // il fac cu Zalgorithm; in primul rand zalgorithm care ca si idee zvalues; acestea se fac pe un string S;
    // fie z[i] = cea mai lunga secvente ce incepe in i si e la fel cu prefixul de lungime;
    // adica z[i] = x; => ca secventa [i...i+x-1] e la fel cu secventa [1..1+x-1];
    // si pentru a gasi aparatiile fac in felul urmator la pattern mai adaug textul si bag zalgorithm
    // la sfarsit pentru fiecare i > pattern.size() cu z[i] >= parttern.size() am gasit o apartie a patternului in text
    // acum zvalues le fac in felul urmator; cazul particular z[1] = S.size();
    // asa ca incep de la pozitia 2; pe parcursul iteratiilor tin 2 indici st si dr; care imi indica cea mai din dreapta
    // secventa gasita pana la pasul curent care apare in prefix( fie ea zBox);
    // bun z[i] il aflu pe baza lui i-1; mai exact o sa am 2 cazuri iar in al 2 lea caz o sa am 3
    // primul caz; dr < i => o sa compar de la pozitia i pana cand gasesc o nepotrivire;
    // al 2 lea caz; dr >= i; aici am asa ; definesc dr2 = 1 + (dr-st+1) - 1 si i2 ca fiind 1 + ( dr - k + 1 ) - 1 si
    //fie A =  secventa [i..dr]; ea evident == cu [i1..dr2];
    // 2.a) z[i2] < A.size() ( == dr2 - i2 + 1) => z[i] = z[i2]; e evident pentru ca inseamna ca cea lunga secventa e < ca si A.size() deci de la A.size()+1 nu concind caracter;
     // 2.b) z[i2] > A.size() => z[i] = A.size(); e egal cu A.size() pt ca; hai sa pp ca nu e la fel asta inseamna ca S[dr+1] == cu S[dr2+1] deci secventa st...dr (cand am facuto) putea fi marita si nu a fost
     // => z[i] = A.size();
    // 2.c) z[i2] == A.size() => aici o sa caut o nepotrivire de la dr+1 incolo pt ca nu pot deduce nici cum ce urmeaza
    Zvalues();

    int p = P.size(); int sz = 0;
    for(int i=p+1; i<S.size(); ++i){
        if (z[i] >= p){// >= pt ca s-ar putea ca secventa de incepe pe i sa fie mai mare ca si p
            if (sz < 1000){
                rez[++sz] = i-p-1;// problema din arhiva le are indexate de la 0
            }else ++sz;
        }
    }
    g << sz << "\n";
    sz = min(sz, 1000);
    for(int i=1; i<=sz; ++i){
        g << rez[i] << " ";
    }
    g << "\n";
}

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

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

    return 0;
}