Cod sursa(job #3310505)

Utilizator SkibidiCezarCezar Bolba SkibidiCezar Data 14 septembrie 2025 13:44:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 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 = 0;
    for(int i = 0; i < nrb; i++){
        while(p > 0 && a[p] != b[i]){
            //cout << p << " ";
            p = lps[p-1];
        }
        if(b[i] == a[p]){
            p++;
        }
        if(p == nra){
            n++;
            poz.push_back(i - nra + 1);
            p = lps[p-1];
        }
        //cout << p << "\n";
    }
    fout << n << "\n";
    for(int i = 0; i < min((int)poz.size(), 1000); i++){
        fout << poz[i] << " ";
    }
    return 0;
}