Cod sursa(job #3239634)

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

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-(1LL*hsh[i-lg].f*pw[lg].f)%MOD1+1LL*MOD1*MOD1)%MOD1;
  val.s=(hsh[i].s-(1LL*hsh[i-lg].s*pw[lg].s)%MOD2+1LL*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=(1LL*pw[i-1].f*B)%MOD1;
    pw[i].s=(1LL*pw[i-1].s*B)%MOD2;
  }
  for(i=0; s[i]; i++)
  {
    lg++;
    hs.f=((1LL*hs.f*B)%MOD1+(s[i]+1))%MOD1;
    hs.s=((1LL*hs.s*B)%MOD2+(s[i]+1))%MOD2;
  }
  hsh[0]={0, 0};
  for(i=0; t[i]; i++)
  {
    hsh[i+1].f=((1LL*hsh[i].f*B)%MOD1+(t[i]+1))%MOD1;
    hsh[i+1].s=((1LL*hsh[i].s*B)%MOD2+(t[i]+1))%MOD2;
    if(i+1>=lg && check(i+1, lg)) ans.push_back(i-lg+1);
  }
  cout<<ans.size()<<'\n';
  int cnt=0;
  for(auto i:ans)
  {
    cnt++;
    cout<<i<<' ';
    if(cnt==1000) break;
  }
  return 0;
}