Cod sursa(job #3321226)

Utilizator andreiaramaArama Andrei Robert andreiarama Data 8 noiembrie 2025 17:30:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string a, b;;

int z[4000001];

int main() {
    cin>>a>>b;
    string s=a+'#'+b;
    int l=0, r=0;
    for(int i=0;i<s.size();i++) {
        if(i<=r) {
            z[i]=min(r-i+1, z[i-l]);  
        }
        while(i+z[i]<s.size() && s[z[i]]==s[i+z[i]])
        {
            z[i]++;
        }
        if(i+z[i]-1>r) {
            l=i;
            r=i+z[i]-1;
        }
    }
    int matches=0;
    vector<int> m;
    for(int i=a.size()+1;i<s.size();i++) {
        if(z[i]==a.size()){matches++;m.push_back(i-a.size()-1);}
    }
    cout<<matches<<'\n';
    for(auto match:m) {
        cout<<match<<' ';
    }
    return 0;
}