Cod sursa(job #2907764)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 31 mai 2022 16:36:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nr = 1e9;
int mod[2] = {nr + 7,nr + 9};
int h[2],h2[2],p[2] = {1,1};
char v[2000000];
char v2[2000000];
int ans[1000],cnt = 0;
void add(int a){
  if(cnt < 1000){
    ans[cnt] = a;
  }
  cnt++;
}
int main()
{
  int n = 0,i,m = 0,j;
  v[n++] = fin.get();
  while(v[n - 1] != '\n'){
    v[n++] = fin.get();
  };
  n--;
  v2[m++] = fin.get();
  while(v2[m - 1] != '\n'){
    v2[m++] = fin.get();
  };
  m--;
  for(i = 0;i < n;i++){
    for(j = 0;j < 2;j++){
      h[j] = (1ll*h[j]*256 + v[i])%mod[j];
      h2[j] = (1ll*h2[j]*256 + v2[i])%mod[j];
      p[j] = 1ll*p[j]*256%mod[j];
    }
  }
  for(i = n;i < m;i++){
    ///check equality
    j = 0;
    while(j < 2 && h[j] == h2[j]){
        j++;
    }
    if(j == 2){
      add(i - n);
    }
    ///add v2[i]
    for(j = 0;j < 2;j++){
      h2[j] = (1ll*h2[j]*256 + v2[i])%mod[j];
      ///remove v2[i - n]
      h2[j] = (0ll + h2[j] - 1ll*(v2[i - n])*p[j])%mod[j];
      if(h2[j] < 0)h2[j]+=mod[j];
    }
  }
  j = 0;
  while(j < 2 && h[j] == h2[j]){
    j++;
  }
  if(j == 2){
    add(i - n);
  }
  fout<<cnt<<'\n';
  for(i = 0;i < min(cnt,1000);i++){
    fout<<ans[i]<<' ';
  }
  return 0;
}