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