map
map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map（允许重复的键）。本文用：单键无序map。
LeetCode2781:最长合法子字符串的长度
给你一个字符串 word 和一个字符串数组 forbidden 。
如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。
请你返回字符串 word 的一个 最长合法子字符串 的长度。
子字符串 指的是一个字符串中一段连续的字符，它可以为空。
示例 1：
输入：word = “cbaaaabc”, forbidden = [“aaa”,“cb”]
输出：4
解释：总共有 11 个合法子字符串：“c”, “b”, “a”, “ba”, “aa”, “bc”, “baa”, “aab”, “ab”, “abc” 和 “aabc”。最长合法子字符串的长度为 4 。
其他子字符串都要么包含 “aaa” ，要么包含 “cb” 。
示例 2：
输入：word = “leetcode”, forbidden = [“de”,“le”,“e”]
输出：4
解释：总共有 11 个合法子字符串：“l” ，“t” ，“c” ，“o” ，“d” ，“tc” ，“co” ，“od” ，“tco” ，“cod” 和 “tcod” 。最长合法子字符串的长度为 4 。
所有其他子字符串都至少包含 “de” ，“le” 和 “e” 之一。
参数范围：
1 <= word.length <= 105
word 只包含小写英文字母。
1 <= forbidden.length <= 105
1 <= forbidden[i].length <= 10
forbidden[i] 只包含小写英文字母。
滑动窗口+离线查询+map
时间复杂度😮(nmm+nlogn+n)。m = max(forbidden[i].length)为10
第一步：如果s[left,right]等于 forbidden中任何一个字符串，记录在vLeftRight中。本问题等效与：不能包括任意[left,right]的最长子串。
第二步：排序vLeftRight。
第三步：从大到小枚举合法子串的左边界i，计算最大右边界j。
如果s[left,right]等于某个禁止串
| left<i | 无论j为何值，都不会包括对应的禁止串，因为s[left]不在对应的子串中 |
| left>=i | j的取值范围为[i,right)，不能取值right ，否则s[left,right] 就在word[i,j]中。如果多个无法合法的right，取最小值。如果没有合法的right，取m_c。 |
离线查询
由于vLeftRight 已经按left排序，每次处理i之前，先用left >= i的right更新iMin。
代码
核心代码
class Solution { public: int longestValidSubstring(string word, vector<string>& forbidden) { m_c = word.length(); std::unordered_set<string> setHas(forbidden.begin(), forbidden.end()); vector<pair<int, int>> vLeftRight; for (int len = 1; len <= 10; len++) { for (int left = 0; left + len <= m_c; left++) { if (setHas.count(word.substr(left, len))) { vLeftRight.emplace_back(left, left + len - 1); } } } sort(vLeftRight.begin(), vLeftRight.end()); int iRet = 0; int iMin = m_c; for (int i = m_c - 1; i >= 0; i--) { while (vLeftRight.size() && (vLeftRight.back().first >= i)) { iMin = min(iMin, vLeftRight.back().second); vLeftRight.pop_back(); } iRet = max(iRet, iMin - i); } return iRet; } int m_c; };
字典树
可以利用字典树，将第一步的时间复杂度降到O(nm)。
template<class TData, TData defData,int iTypeNum = 26, TData cBegin = 'a'> class CTrie { public: CTrie() { m_iID = s_ID++; } int GetLeadCount() { return m_iLeafCount; } template<class IT> int Add(IT begin, IT end) { int iLeve = 0; CTrie* pNode = this; for (; begin != end; ++begin) { pNode = pNode->AddChar(*begin); pNode->m_iLeve = iLeve++; } if (-1 == pNode->m_iLeafID) { pNode->m_iLeafID = ++m_iLeafCount; } return pNode->m_iLeafID; } template<class IT> CTrie* Search(IT begin, IT end) { if (begin == end) { return this; } if ('.' == *begin) { for (auto& ptr : m_vPChilds) { if (!ptr) { continue; } auto pSearch = ptr->Search(begin + 1, end); if (pSearch) { return pSearch; } } return nullptr; } auto ptr = GetChild(*begin); if (nullptr == ptr) { return nullptr; } return ptr->Search(begin + 1, end); } CTrie* AddChar(TData ele) { if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } const int index = ele - cBegin; auto ptr = m_vPChilds[index]; if (!ptr) { m_vPChilds[index] = new CTrie(); } return m_vPChilds[index]; } CTrie* GetChild(TData ele)const { if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } return m_vPChilds[ele - cBegin]; } protected: int m_iID; public: int m_iLeafID=-1; protected: int m_iLeve=-1; inline static int s_ID = 0; int m_iLeafCount = 0; CTrie* m_vPChilds[iTypeNum] = { nullptr }; }; class Solution { public: int longestValidSubstring(string word, vector<string>& forbidden) { m_c = word.length(); CTrie<char,'a'> trie; for (const auto& s : forbidden) { trie.Add(s.begin(), s.end()); } vector<pair<int, int>> vLeftRight; for (int left = 0; left < m_c ; left++) { CTrie<char,'a'>* p = ≜ for (int len = 1; left + len <= m_c; len++) { p = p->GetChild(word[left + len - 1]); if (nullptr == p) { break; } if (p->m_iLeafID > 0) { vLeftRight.emplace_back(left, left + len - 1); } } } sort(vLeftRight.begin(), vLeftRight.end()); int iRet = 0; int iMin = m_c; for (int i = m_c - 1; i >= 0; i--) { while (vLeftRight.size() && (vLeftRight.back().first >= i)) { iMin = min(iMin, vLeftRight.back().second); vLeftRight.pop_back(); } iRet = max(iRet, iMin - i); } return iRet; } int m_c; };
2023年7月版
class Solution { public: int longestValidSubstring(string word, vector& forbidden) { m_pHash = std::make_shared< CHashStr<>>(word,26); std::unordered_set setCode[11]; for (const string& s : forbidden) { const int len = s.length(); CHashStr< > hash(s,26); auto llCode = hash.GetHashExincludeRight(len); setCode[len].emplace(llCode); } std::map mEndLen; for (int i = 0; i < word.size(); i++) { for (int len = 1; len <= 10 ; len++) { const int end = i + len; if (end > word.size()) { continue; } int llCode = m_pHash->GetHashExincludeRight(i, end); if (setCode[len].end() != setCode[len].find(llCode)) { //目标串不能包括[1,i+len) mEndLen[i+len] = len; break; } } } int begin = 0; int iMaxLen = 0; for (const auto& it : mEndLen) { const int iCurLen = it.first - begin-1; iMaxLen = max(iMaxLen, iCurLen); begin = max(begin,it.first - it.second+ 1); } iMaxLen = max(iMaxLen, (int)word.size() - begin); return iMaxLen; } std::shared_ptr< CHashStr<> > m_pHash; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
