链接1044. 最长重复子串 - 力扣LeetCode题解class Solution { public: string longestDupSubstring(string s) { int len s.size(); if (len 0) { return ; } int left 0; int right len - 1; while (left 1 right) { int mid left (right - left) / 2; int begin 0; bool success calc(s, mid, begin); if (success) { left mid; } else { right mid; } } int begin 0; if (calc(s, right, begin)) { return s.substr(begin, right); } if (calc(s, left, begin)) { return s.substr(begin, left); } return ; } bool calc(const std::string s, int len, int begin) { int base 26; int power 1; int MOD 1000000; for (int i 0; i len - 1; i) { power (power * base) % MOD; } unordered_mapint, int table; int hash 0; for (int i 0; i len; i) { // hash * base 就是base进制 hash (hash * base (s[i] - a)) % MOD; } table[hash] 0; /*判断是否有重复串出现*/ for (int i 1; i len - 1 s.size(); i) { hash ((hash - (s[i - 1] - a) * power % MOD MOD) % MOD * base (s[i len - 1] - a) % MOD) % MOD; if (table.find(hash) ! table.end() s.substr(table[hash], len) s.substr(i, len)) { /*hash可能有冲突还需要每个字符check下*/ begin table[hash]; return true; } // 没有重复更新开始位置 table[hash] i; } return false; } };
