Cod sursa(job #2238689)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 7 septembrie 2018 08:48:15
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;

void zArrcalc(string pat, int Z[]){
    int n = pat.size();
    int L, R, k;
    L = R = 0;
    for(int i = 1; i < n; ++i)
    {
        if (i > R)
        {
            L = R = i;
            while(R<n && pat[R-L] == pat[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<n && pat[R-L] == pat[R])
                    R++;
                Z[i] = R-L;
                R--;
            }
        }
    }
}

void Zsearch(string pat, string txt){
    string concat = pat + "$" + txt;
    int l = concat.size();
    int Z[l];
    zArrcalc(concat, Z);
    for(int i = 0; i < l; ++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;
}