Cod sursa(job #3310495)

Utilizator SkibidiCezarCezar Bolba SkibidiCezar Data 14 septembrie 2025 13:19:48
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[2000005];
char b[2000005];
int lps[2000005];
int n, nra, nrb, p;
vector <int> poz;

int main()
{
    fin >> a >> b;
    nra = strlen(a);
    nrb = strlen(b);
    for(int i = 1; i < nra; i++){
        p = lps[i-1];
        while(p > 0 && a[i] != a[p]){
            p = lps[p] - 1;
        }
        if(a[i] == a[p]){
            lps[i] = p + 1;
        }
        //cout << lps[i] << "\n";
    }
    p = -1;
    for(int i = 0; i < nrb; i++){
        if(a[p+1] == b[i]){
            p++;
            if(p == nra - 1){
                n++;
                poz.push_back(i - nra + 1);
                p = lps[p] - 1;
            }
        }
        else{
            while(p >= 0 && a[p] != b[i]){
                //cout << p << " ";
                p = lps[p] - 1;
            }
        }
        //cout << p << "\n";
    }
    fout << n << "\n";
    for(int i = 0; i < poz.size(); i++){
        fout << poz[i] << " ";
    }
    return 0;
}