Cod sursa(job #3163448)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 31 octombrie 2023 14:39:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    string s, t; fin >> s >> t;
    int size1 = s.size();
    s += '#';
    s += t;
    //cout << "Noul s = " << s << endl;

    int n = s.size();
    int p[s.size()];
    p[0] = 0;
    int k = 0;
    int cnt = 0;
    vector <int> poz;
    for(int i = 1; i < n; i++){
        while(k > 0 && s[k] != s[i]){
            k = p[k - 1];
        } 

        if(s[k] == s[i]) k++;
        p[i] = k;

        if(p[i] == size1){
            cnt++;
            poz.push_back(i - size1 + 1);
        }
    }
    fout << cnt << endl;
    for(int i = 0; i < poz.size(); i++) fout << poz[i] - size1 - 1 << " ";
    fout << endl;


    return 0;
}