Алгоритмҳои ҳешкунии сатрҳо
Ҳешкунӣ кардани як сатр табдил додани сатр ба як адад (ҳеш) мебошад.
Функсияи ҳеш бояд детерминистӣ бошад: ҳамон як сатр ҳамеша ҳамон як ҳешро ҳосил мекунад.
Яке аз таърифҳои маъмултарини ҳеши полиномӣ барои сатр :
Дар куҷо:
Мисол:
Барои сатрҳои дароз ҳешҳо калон мешаванд, бинобар ин мо боқимондаро аз як адади содаи калон мегирем:
Коллизияҳо (сатрҳои гуногун бо як ҳеш) имконпазиранд, аммо бо параметрҳои хуб кам рух медиҳанд.
Дода шудааст:
Ҳамаи -ҳоро ёбед, ки:
Соддалавҳона:
Ҳешкунӣ:
Муайян кунед:
Равзанаи навбатӣ:
Муносибат:
Пас мо метавонем дар навсозӣ кунем.
const int P = 29;
const int M = 1e9 + 7;
vector<int> pw;
void init(int N) {
pw.resize(N);
pw[0] = 1;
for (int i = 1; i < N; i++) {
pw[i] = 1LL * pw[i - 1] * P % M;
}
}
int hash_string(const string& s) {
int res = 0;
for (int i = 0; i < (int)s.size(); i++) {
int x = s[i] - 'a' + 1;
res = (res + 1LL * x * pw[i]) % M;
}
return res;
}
int hash_string(const string& s) {
int res = 0;
for (int i = (int)s.size() - 1; i >= 0; i--) {
int x = s[i] - 'a' + 1;
res = (1LL * res * P + x) % M;
}
return res;
}
vector<int> find_occurrences(string s, string t) {
int n = s.size();
int m = t.size();
if (m > n) return {};
// hash of pattern
int hashT = 0;
for (int i = 0; i < m; i++) {
hashT = (hashT + 1LL * (t[i] - 'a' + 1) * pw[i]) % M;
}
vector<int> hashS(n - m + 1);
// last window
for (int i = 0; i < m; i++) {
hashS[n - m] = (hashS[n - m] +
1LL * (s[n - m + i] - 'a' + 1) * pw[i]) % M;
}
// rolling backwards
for (int i = n - m - 1; i >= 0; i--) {
hashS[i] = (s[i] - 'a' + 1);
hashS[i] = (hashS[i] + 1LL * hashS[i + 1] * P) % M;
hashS[i] = (hashS[i] - 1LL * (s[i + m] - 'a' + 1) * pw[m]) % M;
hashS[i] = (hashS[i] + M) % M;
}
vector<int> res;
for (int i = 0; i <= n - m; i++) {
if (hashS[i] == hashT)
res.push_back(i);
}
return res;
}