Cod sursa(job #3239635)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 7 august 2024 03:07:51
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 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;
vector <int> ans;

bool check(int i, int lg)
{
  pair<int, int> val;
  val.f=(hsh[i].f-(1LL*hsh[i-lg].f*pw.f)%MOD1+1LL*MOD1*MOD1)%MOD1;
  val.s=(hsh[i].s-(1LL*hsh[i-lg].s*pw.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={1, 1};
  for(i=0; s[i]; i++)
  {
    lg++;
    pw.f=(pw.f*B)%MOD1;
    pw.s=(pw.s*B)%MOD2;
    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;
}