Cod sursa(job #2298431)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 8 decembrie 2018 10:17:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 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 (int i = 0; i < sol.size() && i < 1000; i++)
        g << sol[i] - pat.size() - (pat.size() - 1) - 1 << " ";
    g << "\n";
    return 0;
}