Cod sursa(job #3141565)

Utilizator divadddDavid Curca divaddd Data 14 iulie 2023 16:08:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6+2;
string a,b;
int n,m,p[NMAX];

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int main()
{
    getline(fin, a);
    getline(fin, b);
    n = a.size();
    m = b.size();
    a = "$"+a+"$";
    b = "#"+b+"#";
    p[1] = 0;
    int l = 0;
    for(int i = 2; i <= n; i++){
        while(l != 0 && a[i] != a[l+1]){
            l = p[l];
        }
        if(a[i] == a[l+1]){
            l++;
        }
        p[i] = l;
    }
    l = 0;
    vector<int> ans;
    for(int i = 1; i <= m; i++){
        while(l != 0 && b[i] != a[l+1]){
            l = p[l];
        }
        if(b[i] == a[l+1]){
            l++;
        }
        if(l == n){
            ans.push_back(i-n);
            l = p[l];
        }
    }
    fout << ans.size() << "\n";
    for(int i = 0; i < ans.size() && i < 1000; i++){
        fout << ans[i] << " ";
    }
    return 0;
}