Cod sursa(job #3239628)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 7 august 2024 02:58:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#define f first
#define s second
const int NMAX=2e6+5;
const int B=31;
const int MOD1=1e9+7;
const int MOD2=666013;

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

char s[NMAX], t[NMAX];
pair<int, int> hsh[NMAX], hs, pw[NMAX];
vector <int> ans;

bool check(int i, int lg)
{
  pair<int, int> val;
  val.f=(hsh[i].f-(hsh[i-lg].f*pw[lg].f)%MOD1+MOD1)%MOD1;
  val.s=(hsh[i].s-(hsh[i-lg].s*pw[lg].s)%MOD2+MOD2)%MOD2;
  return (val==hs);
}

int main()
{
  int i, lg=0;
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin>>s>>t;
  pw[0]={1, 1};
  for(i=1; s[i-1] || t[i-1]; i++)
  {
    pw[i].f=(pw[i-1].f*B)%MOD1;
    pw[i].s=(pw[i-1].s*B)%MOD2;
  }
  for(i=0; s[i]; i++)
  {
    lg++;
    hs.f=((hs.f*B)%MOD1+(s[i]-'A'+1))%MOD1;
    hs.s=((hs.s*B)%MOD2+(s[i]-'A'+1))%MOD2;
  }
  hsh[0]={0, 0};
  for(i=0; t[i]; i++)
  {
    hsh[i+1].f=((hsh[i].f*B)%MOD1+(t[i]-'A'+1))%MOD1;
    hsh[i+1].s=((hsh[i].s*B)%MOD2+(t[i]-'A'+1))%MOD2;
    if(i+1>=lg && check(i, lg)) ans.push_back(i-lg);
  }
  cout<<ans.size()<<'\n';
  int cnt=0;
  for(auto i:ans)
  {
    cnt++;
    cout<<i<<' ';
    if(cnt==1000) break;
  }
  return 0;
}