Cod sursa(job #1199600)

Utilizator vendettaSalajan Razvan vendetta Data 19 iunie 2014 19:50:52
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

class ZAlgorithm{
public:
    ZAlgorithm(){}
    ZAlgorithm(const string& text){
        //cout << text << "\n";
        this->S = text;
        this->makeZValues();
    }
    vector<int>& getZValues(){
        return this->zValues;
    }
private:
    vector<int> zValues;
    string S;
    int compara(const int &x,const int &y){
        int cnt = 0;
        for(int i=x, j=y; j<(int)S.size(); ++i, ++j){
            if(S[i] != S[j]) return cnt;
            ++cnt;
        }
        return cnt;
    }
    void makeZValues(){
        zValues.assign((int)S.size(), 0);
        zValues[0] = S.size();
        int L = -1; int R = -1;
        for(int i=1; i<S.size(); ++i){
            if (i > R){
                zValues[i] = compara(0, i);
                if (zValues[i] != 0){
                    L = i; R = i + zValues[i]- 1;
                }
            }else {
                int lungA = R - L + 1; int lungB = R - i + 1;
                int R2 = 0 + lungA - 1; int i2 = R2 - lungB + 1;
                if (zValues[i2] < lungB){
                    zValues[i] = zValues[i2]; continue;
                }
                zValues[i] = lungB + compara(lungB, R+1);
                if (i + zValues[i]-1 > R){
                    L = i; R = i + zValues[i] - 1;
                }
            }
        }
    }
};

int main(){
    ifstream f("strmatch.in");
    string text, pattern;
    getline(f, pattern);
    getline(f, text);
    string S = pattern + text;
    ZAlgorithm *X = new ZAlgorithm(S);
    vector<int> z = X->getZValues();
    vector<int> ans;
    int cnt = 0;
    for(int i=(int)pattern.size(); i<S.size(); ++i){
        if (z[i] >= pattern.size()){
            ++cnt;
            if(ans.size() < 1000) ans.push_back(i-(int)pattern.size());
        }
    }
    f.close();
    ofstream g("strmatch.out");
    g << cnt << "\n";
    for(int i=0; i<(int)ans.size(); ++i){
        g << ans[i] << " ";
    }
    g.close();
}