Cod sursa(job #1201968)

Utilizator vendettaSalajan Razvan vendetta Data 26 iunie 2014 15:40:21
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int main(){
    ifstream f("strmatch.in");
    string text, pattern;
    getline(f, pattern);
    getline(f, text);
    int patternSize = (int)pattern.size();
    pattern += text;

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