Cod sursa(job #1559534)

Utilizator vendettaSalajan Razvan vendetta Data 30 decembrie 2015 23:47:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 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<(int)S.size(); ++i, ++j){
        if(S[i] != S[j]) return cnt;
        ++cnt;
    }
    return cnt;
}

void bagaZvalues(){
    S = P + T;
    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);
            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);
            if (i + z[i]-1 > R){
                L = i; R = 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;
}