Cod sursa(job #3327211)

Utilizator radu._.21Radu Pelea radu._.21 Data 2 decembrie 2025 19:51:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>



using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern,sir,s;
int rez = 0;
int kmp[50000001];
int main(){
    fin>>pattern;
    fin>>sir;
    s = pattern + "$" + sir;
    if (pattern.size() > sir.size()){
        fout<<0;
        return 0;
    }
    kmp[0] = 0;
    for(int i =  1; i < s.size(); i++){
        int p = kmp [i-1];
        while(s[i] != s[p] && p > 0){
            p = kmp[p-1];
        }
        if(s[i] == s[p])
            p++;
        kmp[i] = p;
    }
    vector<int>ans;
    for(int i = pattern.size() + 1; i < s.size(); i++){
        if(kmp[i] == pattern.size()){
            rez++;
            if(rez <=1000)
            ans.push_back(i - 2 * pattern.size());
        }

    }
    fout<<rez<<'\n';
    for(auto x : ans)
        fout<<x<<" ";
    return 0;
}