Cod sursa(job #2189578)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 28 martie 2018 17:25:04
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<cstdio>
#include<cstring>
const int BASE = 68;
const int MOD = 100007;
const int NMAX = 2000000;
int hashPref[1 + NMAX];
int powBase[1 + NMAX];
int sol[1 + NMAX];
char A[1 + NMAX];
char B[1 + NMAX];
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] + MOD - hashPref[i - 1] * powBase[j - (i - 1)] % MOD) % 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);
  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 <= lenA + 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)
      sol[++total] = i;
  }
  printf("%d\n",total);
  for(int i = 1; i <= total ; i ++)
    printf("%d ",sol[i]);
  hasha =  hashuri(A);


}