Cod sursa(job #932260)

Utilizator vendettaSalajan Razvan vendetta Data 28 martie 2013 19:56:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 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, S;
int z[nmax*2], rez[nmax];

void citeste(){
    getline(f, P);
    getline(f, T);
}

inline int compara(int x, int y){
    int cnt = 0;
    for(int i=x, j=y; j<S.size(); ++i, ++j){
        if(S[i] != S[j]) return cnt;
        ++cnt;
    }
    return cnt;
}

void bagaZvalues(){
    // z[i] = cea mai lunga secventa ce incepe pe pozitia i si e prefix la secventa initiala
    S = P + T;
    z[0] = S.size();
    int st = -1; int dr = -1;
    for(int i=1; i<S.size(); ++i){
        if (i > dr){// e in afara zBox-ului
            z[i] = compara(0, i);
            if (z[i] != 0){
                st = i; dr = i + z[i]- 1;
            }
            continue;
        }else {
            int lungAlpha = dr - st + 1; int lungBeta = dr - i + 1;
            int dr2 = 0 + lungAlpha - 1; int i2 = dr2 - lungBeta + 1;
            if (z[i2] < lungBeta){
                z[i] = z[i2]; continue;
            }
            if (z[i2] > lungBeta){
                z[i] = lungBeta; continue;
            }
            z[i] = lungBeta + compara(lungBeta, dr+1);
            if (i + z[i]-1 > dr){
                st = i; dr = i + z[i] - 1;
            }
        }
    }
}

void rezolva(){
    bagaZvalues();

    for(int i=P.size(); i<S.size(); ++i){
        //cout << z[i] << " ";
        if (z[i] >= P.size()){
            rez[++rez[0]] = i - P.size();
        }
    }
    g << rez[0] << "\n";
    //cout << rez[0] << "\n";
    rez[0] = min(rez[0], 1000);
    for(int i=1; i<=rez[0]; ++i){
        //cout << rez[i] << " ";
        g << rez[i] << " ";
    }
    g << "\n";
}

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

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

    return 0;
}