## 课后小视频之字符串查找之 Rabin Karp 算法 算法视频QQ\_1603159172 这种算法的本质是用hash function把字符串之间的比较由O(m)长的时间变为O(1) ### hash function 哈希表就是个大数组, hash function是个把字符串, float, double, int都转换到数组一个位置的mapping. #### ABCDE \= (a \* 31^4 + b \* 31^3 + c \* 31^2 + d \* 31 + e) % 10^6 其中31是个经验值, hash size 10^6, 越大越不容易重, 越小越容易冲突, 所以选一个不越界的大的值 如果用int的话, 保证 31 \* 10^6不越界. 如果用10^8的话, 就需要long int 了 key到value唯一, 反之不成立.  abc 只等于123, cde也只等与123, 但是123对应两个string ```cpp #include <iostream> #include <string> using namespace std; bool matchStr(const string& str, const string& match) { /** * abcd * (a*31^3 + b*31^2 + c*31^1 + d) % 10^6 */ int Base = 1000000; int len = match.size(); int code = 0; int power = 1; for (auto c : match) { code = (code * 31 + c) % Base; power = (power * 31) % Base; } int hash = 0; for (int i = 0; i < str.size(); i++) { hash = (hash * 31 + str[i]) % Base; if (i < len - 1) continue; if (i >= len) { hash = hash - str[i - len] * power; if (hash < 0) hash += Base; // str[i - len] * power > Base, +Base是上面 %Base 取余减多的 } if (hash == code) { if (match.compare(str.substr(i - len + 1, len)) == 0) { return true; } } } return false; } int main() { string match, str; while (cin >> match >> str) { bool isMatch = matchStr(str, match); if (isMatch) { cout << "true" << endl; } else { cout << "false" << endl; } } return 0; } ``` #include <iostream> #include <vector> using namespace std; struct Maxheap { int capacity_; int count_; vector<int> data; Maxheap(int capacity) : capacity_(capacity), count_(0) { data = vector<int>(capacity_); } void push(int val) { if (count_ < capacity_) { data[count_] = val; shift_up(count_++); } else { if (val < data[0]) { data[0] = val; shift_down(0); } } } private: void shift_up(int k) { while ( (k - 1) / 2) { int parent = (k - 1) / 2; if (data[parent] >= data[k]) break; swap(data[parent], data[k]); k = parent; } } void shift_down(int k) { while ((k + 1) * 2 < count_) { int max = k; int left = (k + 1) * 2; if (data[left] > data[max]) { max = left; } if (left + 1 < count_ && data[left + 1] > data[max]) { max = left + 1; } if (max == k) { break; } swap(data[k], data[max]); k = max; } } }; int main() { int N, K; while (cin >> N >> K) { Maxheap heap(K); int n; for (int i = 0; i < N; i++) { cin >> n; heap.push(n); } for (auto& x : heap.data) { cout << x << " "; } cout << endl; } return 0; }