Cod sursa(job #2877454)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 24 martie 2022 19:18:07
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 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 = 0, j = 1;
    while (j < n) {
        if (pat[i] == pat[j]) {
            lps[j] = i + 1;
            ++j;
            ++i;
        }
        else {
            i = lps[i - 1];
            if (i == 0)
                lps[j] = 0, ++j;
        }
    }
}

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

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

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

    fout << k << '\n';
    for (int i : ans)
        fout << i << ' ';
    return 0;
}