Cod sursa(job #3321225)

Utilizator andreiaramaArama Andrei Robert andreiarama Data 8 noiembrie 2025 17:27:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 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;
    a+=b;
    int l=0, r=0;
    for(int i=0;i<a.size();i++) {
        if(i<=r) {
            z[i]=min(r-i+1, z[i-l]);  
        }
        while(i+z[i]<a.size() && a[z[i]]==a[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()-b.size();i<a.size();i++) {
        if(z[i]>=a.size()-b.size()){matches++;m.push_back(i-a.size()+b.size());}
    }
    cout<<matches<<'\n';
    for(auto match:m) {
        cout<<match<<' ';
    }
    return 0;
}