Cod sursa(job #2191809)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 3 aprilie 2018 19:31:36
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<cstring>
const int BASE = 80;
const long long MOD = 100007;
const int NMAX = 2000000;
long long hashPref[1 + NMAX];
long long powBase[1 + NMAX];
int sol[1 + NMAX];
char A[1 + NMAX];
char B[1 + NMAX];
int n;
int get_code(char c)
{
  return c - 'A' + 1;
}
int hashuri(char *s)
{
  int ans = 0;
  while(s[0] != '\0')
  {
    ans = (ans * BASE + get_code(s[0])) % MOD;
    s++;
  }
  return ans;
}
int hash_interval(int i, int j) {
  return (hashPref[j] +  100000 * MOD - (hashPref[i - 1] * powBase[j - i + 1]) ) % MOD;
}

int main()
{
  int lenA , lenB , hasha ,total = 0;
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);
  gets(A);  ///CE CAUT
  gets(B);  /// textul propriu-zis
  lenB = strlen(B);
  lenA = strlen(A);
  hasha = hashuri(A);
  n = lenB;
  for (int i = 0; i < lenB; i++)
    hashPref[i] = (hashPref[i - 1] * BASE + get_code(B[i])) % MOD;
  powBase[0] = 1;
  for(int i = 1; i <= n + 3; i ++)
    powBase[i] = (powBase[i - 1] * BASE) % MOD;
  for(int i = 0; i <= lenB - lenA ; i ++)
  {
    if(hash_interval(i , i + lenA - 1) == hasha % MOD)
      sol[++total] = i;
  }
  printf("%d\n",total);
  for(int i = 1; i <= total ; i ++)
    printf("%d ",sol[i]);
  hasha =  hashuri(A);


}