Cod sursa(job #2907780)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 31 mai 2022 16:52:59
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nr = 1e6;
int mod[2] = {nr + 7,nr + 21};
int h[2],h2[2],p[2] = {1,1};
char v[2000001];
char v2[2000001];
int ans[1001],cnt = 0;
void add(int a){
  if(cnt <= 1000){
    ans[cnt] = a;
  }
  cnt++;
}
int main()
{
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  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] = (h[j]*256 + v[i])%mod[j];
      h2[j] = (h2[j]*256 + v2[i])%mod[j];
      p[j] = p[j]*256%mod[j];
    }
  }
  for(i = n;i < m;i++){
    ///check equality
    if(h[0] == h2[0] && h[1] == h2[1]){
      add(i - n);
    }
    ///add v2[i]
    for(j = 0;j < 2;j++){
      h2[j] = (h2[j]*256 + v2[i] - v2[i - n]*p[j])%mod[j];
      if(h2[j] < 0)h2[j]+=mod[j];
    }
  }
  if(h[0] == h2[0] && h[1] == h2[1]){
    add(i - n);
  }
  fout<<cnt<<'\n';
  for(i = 0;i < min(cnt,1000);i++){
    fout<<ans[i]<<' ';
  }
  return 0;
}