Cod sursa(job #2911841)

Utilizator LolluckestarNastasa-Baras Luca Lolluckestar Data 2 iulie 2022 19:41:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define Nmax 2000005

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char p[Nmax], s[Nmax];
int pi[Nmax];
int main()
{
    fin >> p;
    fin >> s;

    ///prefix function
    int n = strlen(p);
    for (int i = 1; i < n; i++)
    {
        int k = pi[i - 1];
        while (k > 0 && p[k] != p[i])
            k = pi[k - 1];
        if (p[k] == p[i])
            k++;
        pi[i] = k;
    }

    ///matching
    int k = 0, m = strlen(s);
    vector <int> sol;
    for (int j = 0; j < m; j++)
    {
        while (k > 0 && p[k] != s[j])
            k = pi[k - 1];
        if (s[j] == p[k])
            k++;

        if (k == n)
            sol.push_back(j - n + 1);
    }

    fout << sol.size() << '\n';
    if (sol.size() > 1000) sol.resize(1000);
    for (auto it : sol)
        fout << it << ' ';
    return 0;
}