链接LintCode 炼码 - 更高效的学习体验题解class Solution { public: /** * param source: A source string * param target: A target string * return: An integer as index */ int strStr2(string source, string target) { // write your code here int base 26; int MOD 1000000; int len target.size(); if (len 0) { return 0; } int m source.size(); if (m len) { return -1; } int power 1; for (int i 0; i len - 1; i) { power (power * 26) % MOD; } int target_hash 0; for (auto ch : target) { target_hash (target_hash * base (ch - a)) % MOD; } int source_hash 0; for (int i 0; i len; i) { source_hash (source_hash * base (source[i] - a)) % MOD; } if (source_hash target_hash) { if (source.substr(len) target) { return 0; } } for (int i 1; i len - 1 m; i) { source_hash ((source_hash - (source[i - 1] - a) * power % MOD MOD) % MOD * base (source[i len - 1] - a)) % MOD; if (source_hash target_hash) { if (source.substr(i, len) target) { return i; } } } return -1; } };二维class Solution { public: /** * param matrix: 主串矩阵 * param pattern: 模式串矩阵 * return: 模式串在主串中出现的次数 */ int findPattern(vectorvectorchar matrix, vectorvectorchar pattern) { int n matrix.size(); // 主串行数 int m matrix[0].size(); // 主串列数 int p pattern.size(); // 模式串行数 int q pattern[0].size(); // 模式串列数 if (n p || m q) return 0; const int BASE 26; const long long MOD 1e9 7; // 1. 计算模式串的二维哈希值 long long pattern_hash 0; for (int i 0; i p; i) { long long row_hash 0; for (int j 0; j q; j) { row_hash (row_hash * BASE (pattern[i][j] - a)) % MOD; } pattern_hash (pattern_hash * BASE row_hash) % MOD; } // 2. 计算每行的滚动哈希 vectorvectorlong long row_hashes(n, vectorlong long(m - q 1, 0)); // 计算 BASE^(q-1) long long power_col 1; for (int j 0; j q - 1; j) { power_col (power_col * BASE) % MOD; } for (int i 0; i n; i) { // 计算第一个窗口的哈希值 long long hash 0; for (int j 0; j q; j) { hash (hash * BASE (matrix[i][j] - a)) % MOD; } row_hashes[i][0] hash; // 滚动哈希 for (int j 1; j q m; j) { hash ((hash - (matrix[i][j-1] - a) * power_col % MOD MOD) % MOD * BASE (matrix[i][jq-1] - a)) % MOD; row_hashes[i][j] hash; } } // 3. 在列方向上使用滚动哈希匹配 long long power_row 1; for (int i 0; i p - 1; i) { power_row (power_row * BASE) % MOD; } int result 0; // 枚举所有可能的起始列 for (int j 0; j q m; j) { // 计算第一个窗口的二维哈希值 long long matrix_hash 0; for (int i 0; i p; i) { matrix_hash (matrix_hash * BASE row_hashes[i][j]) % MOD; } if (matrix_hash pattern_hash) { result; } // 滚动哈希 for (int i 1; i p n; i) { matrix_hash ((matrix_hash - row_hashes[i-1][j] * power_row % MOD MOD) % MOD * BASE row_hashes[ip-1][j]) % MOD; if (matrix_hash pattern_hash) { result; } } } return result; } };// 本题解信息来源于【九章算法】。请勿进行商业转载非商业转载请注明出处。 class Solution { public: /** * param source a source string * param target a target string * return an integer as index */ int strStr2(const char* source, const char* target) { // Write your code here if (source NULL || target NULL) return -1; int m strlen(target); int n strlen(source); if (m 0) return 0; int mod rand() % 1000000 1000000; int hash_target 0; int m26 1; for (int i 0; i m; i) { hash_target (hash_target * 26 target[i] - a) % mod; if (hash_target 0) hash_target mod; } for (int i 0; i m - 1; i) m26 m26 * 26 % mod; int value 0; for (int i 0; i n; i) { if (i m) value (value - m26 * (source[i - m] - a)) % mod; value (value * 26 source[i] - a) % mod; if (value 0) value mod; if (i m - 1 value hash_target) { // you have to double check by directly compare the string char sub[m]; memcpy(sub, source[i - m 1], m); sub[m] \0; if (strcmp(target, sub) 0) { return i - m 1; } } } return -1; } };https://www.jiuzhang.com/problems/info/594
