给出一个字符串 \(s\)，求它最长的至少出现两次的子串的长度。
多组数据，\(|s|\le 5000\)。
不难发现答案有单调性，考虑对字符串哈希并二分，从左往右扫，用哈希表记录当前该长度每种哈希值是否出现过，出现过则可行。
时间复杂度为 \(\mathcal{O}(\sum |s|\log (\sum |s|))\)，空间复杂度为 \(\mathcal{O}(\sum |s|)\)。
UVA1223 Editor
发布时间 2023-11-06 10:43:34作者: 蒟蒻·廖子阳
给出一个字符串 \(s\)，求它最长的至少出现两次的子串的长度。
多组数据，\(|s|\le 5000\)。
不难发现答案有单调性，考虑对字符串哈希并二分，从左往右扫，用哈希表记录当前该长度每种哈希值是否出现过，出现过则可行。
时间复杂度为 \(\mathcal{O}(\sum |s|\log (\sum |s|))\)，空间复杂度为 \(\mathcal{O}(\sum |s|)\)。