Cod sursa(job #3286514)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 14 martie 2025 12:06:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
// 100 Puncte
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char str[2000005], pat[2000005];
int lsp[2000005];
vector<int> sol;
void precompute_lsp() {
    int idx = 0, j=1;
    while (pat[j]!='\0') {
        if (pat[idx]==pat[j]) {
            idx++;
            lsp[j]=idx;
            j++;
        }
        else if (idx>0) {
            idx = lsp[idx-1];
        }
        else {
            j++;
        }
    }
}
void kmp() {
    int idx = 0, j=0;
    while (str[j]!='\0') {
        if (str[j]==pat[idx]) {
            idx++; j++;
            if (pat[idx]=='\0') {
                //Eu puneam if aici
                //ca sa nu am mai mult de 1000 de
                //siruri in sol, dar nu mai afisam
                //numarul lor corect...
                sol.push_back(j-idx);
                idx = lsp[idx-1];
            }
        }
        else if (idx>0) {
            idx = lsp[idx-1];
        }
        else {
            j++;
        }
    }
}
int main()
{
    fin>>pat>>str;
    precompute_lsp();
    kmp();
    fout<<sol.size()<<'\n';
    for (int i=0; i<min((int)sol.size(), 1000); i++)
        fout<<sol[i]<<' ';
    return 0;
}