Cod sursa(job #3337713)

Utilizator iustin.dumiDumitrescu Iustin iustin.dumi Data 29 ianuarie 2026 16:28:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
unsigned long long a1h,a2h,b1h,b2h,i,j,n,m,p1=1,p2=1;
string a,b;
vector<int> sol;
int main()
{ fin>>a;
  fin>>b;
  n=a.size();
  m=b.size();
  for(i=0;i<n;i++)
  {a1h=37*a1h+a[i];
   a2h=31*a2h+a[i];
   b1h=37*b1h+b[i];
   b2h=31*b2h+b[i];
   p1=p1*37;
   p2=p2*31;
  }
  p1/=37;
  p2/=31;
  if(a1h==b1h && a2h==b2h)
     sol.push_back(0);
  for(i=n;i<m;i++)
  {b1h=(b1h-b[i-n]*p1)*37+b[i];
   b2h=(b2h-b[i-n]*p2)*31+b[i];
   if(a1h==b1h && b2h==a2h)
      sol.push_back(i-n+1);
   if(sol.size()>=1000) break;
  }
  fout<<sol.size()<<'\n';
   for(i=0;i<sol.size();i++) fout<<sol[i]<<" ";
    return 0;
}