Cod sursa(job #2119565)

Utilizator catalinlupCatalin Lupau catalinlup Data 1 februarie 2018 14:08:09
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <bits/stdc++.h>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
using namespace std;

ifstream in(INFILE);
ofstream out(OUTFILE);

vector<int> ComputeZVector(string str){
    vector<int> Z(str.size(),0);
    int L=0;
    int R=0;
    for(int k=1;k<str.size();k++){
        if(R<k){
            R=L=k;
            while(R<str.size()&&str[R]==str[R-L])
                R++;
            Z[k]=R-L;
            R--;
        }
        else{
            int k1=k-L;
            if(k1<R-k+1){
                Z[k]=Z[k1];
            }
            else{
                L=k;
                while(R<str.size()&&str[R]==str[R-L])
                    R++;
                Z[k]=R-L;
                R--;
            }
        }
    }
    return Z;
}

vector<int> ZAlgoritm(string haysack,string needle){
    string prepreocess=needle+"$"+haysack;
    vector<int> Z=ComputeZVector(prepreocess);
    vector<int> ret;
   for(int i=needle.size();i<Z.size();i++){
        if(Z[i]==needle.size())
            ret.push_back(i-needle.size()-1);
    }
    return ret;
}

int main()
{
   string needle,haysack;
   vector<int> ret;
    in>>needle>>haysack;
    ret=ZAlgoritm(haysack,needle);
    out<<ret.size()<<"\n";
    for(auto x:ret)
        out<<x<<" ";
    return 0;
}