Cod sursa(job #2298409)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 decembrie 2018 09:50:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string x, pat;

vector<int> phi, sol;
int main()
{
    f >> pat >> x;

    x = pat + "#" + x;

    phi.resize(x.size() + pat.size() + 3, 0);
    for(int i = 1; i < x.size(); i++) {
        int rez = phi[i - 1];

        while(rez && x[i] != x[rez])
            rez = phi[rez - 1];

        if(x[i] == x[rez]) rez++;

        phi[i] = rez;
    }


    for(int i = 0; i < x.size(); i++) {
        if(phi[i] == pat.size()) sol.push_back(i);
    }
    g << sol.size() << "\n";
    for (auto i : sol)
        g << i - pat.size() - (pat.size() - 1) - 1<< " ";
    g << "\n";
    return 0;
}