Clasele 9-10 lecția 6 - 6 nov 2015

Hashuri

const int P1 = 1000000007;
const int P2 = 1000000009;

struct Hash {
  Zn<P1> rest1;
  Zn<P2> rest2;
  int size;

  Hash() {
    rest1 = 0;
    rest2 = 0;
    size = 0;
  }
};

const int MAX_N = 100000;
const int BASE = 253;

Zn<P1> Bases1[1 + MAX_N];
Zn<P2> Bases2[1 + MAX_N];

void init() {
  int i;
  Bases1[0] = 1;
  Bases2[0] = 1;
  for (i = 1; i <= MAX_N; i++) {
    Bases1[i] = Bases1[i - 1] * Zn<P1>(BASE);
    Bases2[i] = Bases2[i - 1] * Zn<P2>(BASE);
  }
}

Hash append(Hash s, char l) {
  s.rest1 = s.rest1 * Zn<P1>(BASE) + Zn<P1>(l);
  s.rest2 = s.rest2 * Zn<P2>(BASE) + Zn<P2>(l);
  s.size++;
  return s;
}

Hash prepend(char l, Hash s) {
  s.rest1 = Zn<P1>(l) * Bases1[s.size] + s.rest1;
  s.rest2 = Zn<P2>(l) * Bases2[s.size] + s.rest2;
  s.size++;
  return s;
}

Hash join(Hash s1, Hash s2) {
  s1.rest1 = s1.rest1 * Bases1[s2.size] + s2.rest1;
  s1.rest2 = s1.rest2 * Bases2[s2.size] + s2.rest2;
  s1.size += s2.size;
  return s1;
}

bool equals(Hash s1, Hash s2) {
  return s1.rest1 == s2.rest1 && s1.rest2 == s2.rest2 && s1.size == s2.size;
}

Hash eraseFromEnd(Hash s, char l) {
  s.rest1 = (s.rest1 - Zn<P1>(l)) / Zn<P1>(BASE);
  s.rest2 = (s.rest2 - Zn<P2>(l)) / Zn<P2>(BASE);
  s.size--;
  return s;
}

Hash eraseFromBeginning(char l, Hash s) {
  s.rest1 = s.rest1 - Zn<P1>(l) * Bases1[s.size - 1];
  s.rest2 = s.rest2 - Zn<P2>(l) * Bases2[s.size - 1];
  s.size--;
  return s;
}

void dump(Hash h) {
  printf("%d %d %d\n", (int)h.rest1, (int)h.rest2, h.size);
}

1354 - Palindrome. Again Palindrome

const int SIZE = 10000;

char sir[2 * SIZE + 1];

int main() {
  init();
  int i;
  scanf("%s", sir);
  Hash normal, invers;
  int n = strlen(sir);
  int sol = n;
  for (i = n - 1; i >= 1; i--) {
    normal = prepend(sir[i], normal);
    invers = append(invers, sir[i]);
    //dump(normal);
    //dump(invers);
    if (equals(invers, normal)) {
      sol = i;
    }
  }
  for (i = sol - 1; i >= 0; i--) {
    sir[n] = sir[i];
    n++;
  }
  sir[n] = 0;
  //printf("%d\n", sol);
  printf("%s\n", sir);
  return 0;
}

Temă

Pentru data viitoare veți avea de rezolvat următoarele 2 probleme:

• 1423 - String Tale (Timus);
• 1517 - Freedom of Choice (Timus).