Cod sursa(job #2591475)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 30 martie 2020 16:40:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include<cstdio>
#include<cstring>
const int NMAX = 2000000;
const int MOD1 = 1000159;
const int MOD2 = 1000033;
char a[NMAX + 1];
char b[NMAX + 1];
char v[NMAX + 1];
int main()
{
  int k = 0;
  freopen("strmatch.in" , "r" , stdin);
  freopen("strmatch.out" , "w" , stdout);
  scanf("%s" , a);
  int n = strlen(a);
  scanf("%s" , b);
  int m = strlen(b);
  int putere1 = 76;
  int putere2 = 83;
  int p1 = 1;
  int p2 = 1;
  int hashA1 = a[0] - '0';
  int hashA2 = a[0] - '0';
  int hashB1 = b[0] - '0';
  int hashB2 = b[0] - '0';
  for(int i = 1; i < n ; i ++)
  {
    hashA1 = hashA1 * putere1 + (a[i] - '0') % MOD1;
    hashA2 = hashA2 * putere2 + (a[i] - '0') % MOD2;
    hashB1 = hashB1 * putere1 + (b[i] - '0') % MOD1;
    hashB2 = hashB2 * putere2 + (b[i] - '0') % MOD2;
    p1 = p1 * putere1 % MOD1;
    p2 = p2 * putere2 % MOD2;
  }
  for(int i = 1; i + n - 1 < m ; i ++)
  {
    hashB1 = ((hashB1 - (b[i - 1] - '0') * p1 + MOD1) % MOD1 * putere1 % MOD1 + (b[i + n - 1] - '0')) % MOD1;
    hashB2 = ((hashB2 - (b[i - 1] - '0') * p2 + MOD2) % MOD2 * putere2 % MOD2 + (b[i + n - 1] - '0')) % MOD2;
    if(hashA1 == hashB1 && hashB2 == hashA2)
    {
      v[++k] = i;
    }
  }
  printf("%d\n" , k);
  for(int i = 1; i <= k && i <= 1000 ; i ++)
    printf("%d " , v[i]);
  return 0;
}