Cod sursa(job #2714285)

Utilizator cristiWTCristi Tanase cristiWT Data 1 martie 2021 17:24:36
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>

using namespace std;

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

string t, s;
int k, sol[2000000], p[2000000], L;

int main()
{
    f >> s >> t;

    for (int i=1; i<s.size(); i++){
        while (L != 0 && s[L] != t[i])
            L = p[L];

        if (s[i] == s[L]) L ++;

        p[i] = L;
    }

    L = 0;
    for (int i=0; i<t.size(); i++){
        while (L != 0 && s[L] != t[i]){
            L = p[L];
        }

        if (t[i] == s[L]) L ++;

        if (L == s.size()){
            sol[++ k] = i - s.size() + 1;
            L = p[L - 1];
        }
    }

    g << k << '\n';
    for (int i=1; i <= k; i++)
        g << sol[i] << ' ';
}