Clasele 9-10 lecția 6 - 6 nov 2015
From Algopedia
Jump to navigationJump to searchHashuri
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: