Cod sursa(job #3305960)

Utilizator Maryy_1369Gociu Maria Anastasia Maryy_1369 Data 6 august 2025 11:42:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int z[4000004];
vector<int>v;
int main(){
   string a,b,s;
   cin>>a>>b;
   s+=a+'#'+b;
   int sizea=a.size();
   z[0]=0;
   int bs=0;
   for(int i=1;i<s.size();i++){
      if(i<=bs+z[bs]-1){
         z[i]=min( bs+z[bs]-i , z[i-bs]);
      }
      while(s[i+z[i]]== s[z[i]]){
         z[i]++;
      }
      if(bs+z[bs]< i+z[i])bs=i;
   }

   int cnt=0;
   for(int i=0;i<s.size();i++){
     if(z[i]==a.size()){
        cnt++;
        if(v.size()==1000)continue;
        v.push_back( i-a.size()-1);
     }
   }

   cout<<cnt<<endl;
   for(int i=0;i<v.size();i++){
    cout<<v[i]<<" ";
   }
}