Cod sursa(job #2238690)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 7 septembrie 2018 09:43:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

vector<int> ans;

int Z[4000005];

void ZAlg(string concat){
    int L, R, k;
    L = R = 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{
            k = i - L;
            if(Z[k] < R - i + 1)
                Z[i] = Z[k];
            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 concat = pat + "$" + txt;
    ZAlg(concat);
    for(int i = 0; i < int(concat.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);
    fout << ans.size() << "\n";
    for(int i = 0; i < int(ans.size()); ++i)
        fout << ans[i] << " ";
    return 0;
}