Cod sursa(job #3263902)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 16 decembrie 2024 22:47:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
using namespace std;

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

int z[4000001];
vector<int> rasp;

void prec(string a) {

    z[0]=0;
    int best=0,i;
    for(i=1;i<a.size();i++) {
        if(i<=best+z[best]){
            z[i]=min(best+z[best]-i,z[i-best]);
        }
        while(a[i+z[i]]==a[z[i]]) z[i]++;
        if(best+z[best]<i+z[i]) best=i;
    }
}


int main()
{
    string a,b;
    int aux,i,cnt=0;
    cin>>a>>b;
    aux=a.size();
    a=a+'$'+b;
    prec(a);
    for(i=0;i<a.size();i++){
        if(z[i]==aux){
            cnt++;
            if(rasp.size()<1000)
                rasp.push_back(i-aux-1);
        }

    }
    cout<<cnt<<"\n";
    for(i=0;i<rasp.size();i++) cout<<rasp[i]<<" ";
    return 0;
}