Cod sursa(job #2907751)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 31 mai 2022 16:13:19
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>

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