Cod sursa(job #2444848)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 1 august 2019 16:40:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

vector<int> ans;

int Z[4000005];

void ZAlg(string concat){
    int L = 0, R = 0, d = 0;
    for(int i = 1; i < int(concat.size()); ++i){
        if(i > R){
            L = R = i;
            while(R < int(concat.size()) && concat[R - L] == concat[R]) R++;
            Z[i] = R - L;
            R--;
        }
        else{
            d = i - L;
            if(Z[d] < R - i + 1) Z[i] = Z[d];
            else{
                L = i;
                while(R < int(concat.size()) && concat[R - L] == concat[R]) R++;
                Z[i] = R - L;
                R--;
            }
        }
    }
}

void Zsearch(string pat, string txt){
    string newstr = pat + '>' + txt;
    ZAlg(newstr);
    for(int i = 0; i < int(newstr.size()); ++i){
        if(Z[i] == int(pat.size()))
            ans.push_back(i - pat.size() - 1);
    }
}

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string word, phrase;
    fin >> word >> phrase;
    Zsearch(word, phrase);
    int len = ans.size();
    fout << len << "\n";
    for(int i = 0; i < min(1000, len); ++i)
        fout << ans[i] << " ";
    return 0;
}