Cod sursa(job #3003074)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 15 martie 2023 14:11:54
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<bits/stdc++.h>
#define DIM 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int lps[DIM];
int n, m, i, j, k;
vector <int> sol;
void Compute_LPS(){
    j = 0;
    for(i=1;i<n;i++){
        while(j > 0 && a[i] != a[j])
            j = lps[j - 1];
        if(a[i] == a[j])
            j++;
        lps[i] = j;
    }
}
void Solve(){
    Compute_LPS();
    j = 0;
    for(i=0;i<m;i++){
        while(j > 0 && a[j] != b[i])
            j = lps[j - 1];
        if(a[j] == b[i])
            j++;
        if(j == n){
            sol.push_back(i - n + 1);
            j = lps[j - 1];
        }
    }
}
int main(){
    fin >> a >> b;
    n = a.size();
    m = b.size();
    Solve();
    fout << sol.size() << "\n";
    k = sol.size();
    for(i=0;i<min(k, 1000);i++)
        fout << sol[i] << " ";
}