Cod sursa(job #2882778)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 31 martie 2022 19:47:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

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

const int nmax = 2e6 + 5;
int lps[nmax];
string pat, txt;
vector <int> ans;

void preprocess(int n) {
    int i = 1, len = 0;
    while (i < n) {
        if (pat[i] == pat[len]) {
            ++len;
            lps[i] = len;
            ++i;
        }
        else {
            if (len)
                len = lps[len - 1];
            else {
                lps[i] = 0;
                ++i;
            }
        }
    }
}

int main()
{
    fin >> pat;
    fin >> txt;
    int n = pat.size();
    int m = txt.size();
    preprocess(n);

    ans.push_back(0);
    int i = 0, j = 0, k = 0;
    while (j < m) {
        if (txt[j] == pat[i])
            ++i, ++j;
        else {
            if (i == 0)
                ++j;
            else {
                i = lps[i - 1];
            }
        }

        if (i == n) {
            ++k;
            i = lps[i - 1];
            if (k <= 1000)
            ans.push_back(j - n);
        }
    }

    fout << k << '\n';
    for (int i = 1; i <= min(k, 1000); ++i)
        fout << ans[i] << ' ';


    return 0;
}