【字典樹】【KMP】【C++算法】3045統計前后綴下標對 II

作者推薦

動態規劃的時間復雜度優化

本文涉及知識點

字符串字典樹 KMP 前后綴

LeetCode:3045統計前后綴下標對 II

給你一個下標從 0 開始的字符串數組 words 。
定義一個布爾函數 isPrefixAndSuffix ，它接受兩個字符串參數 str1 和 str2 ：
當 str1 同時是 str2 的前綴（prefix）和后綴（suffix）時，isPrefixAndSuffix(str1, str2) 返回 true，否則返回 false。
例如，isPrefixAndSuffix(“aba”, “ababa”) 返回 true，因為 “aba” 既是 “ababa” 的前綴，也是 “ababa” 的后綴，但是 isPrefixAndSuffix(“abc”, “abcd”) 返回 false。
以整數形式，返回滿足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 為 true 的下標對 (i, j) 的數量。
示例 1：
輸入：words = [“a”,“aba”,“ababa”,“aa”]
輸出：4
解釋：在本示例中，計數的下標對包括：
i = 0 且 j = 1 ，因為 isPrefixAndSuffix(“a”, “aba”) 為 true 。
i = 0 且 j = 2 ，因為 isPrefixAndSuffix(“a”, “ababa”) 為 true 。
i = 0 且 j = 3 ，因為 isPrefixAndSuffix(“a”, “aa”) 為 true 。
i = 1 且 j = 2 ，因為 isPrefixAndSuffix(“aba”, “ababa”) 為 true 。
因此，答案是 4 。
示例 2：

輸入：words = [“pa”,“papa”,“ma”,“mama”]
輸出：2
解釋：在本示例中，計數的下標對包括：
i = 0 且 j = 1 ，因為 isPrefixAndSuffix(“pa”, “papa”) 為 true 。
i = 2 且 j = 3 ，因為 isPrefixAndSuffix(“ma”, “mama”) 為 true 。
因此，答案是 2 。
示例 3：

輸入：words = [“abab”,“ab”]
輸出：0
解釋：在本示例中，唯一有效的下標對是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix(“abab”, “ab”) 為 false 。
因此，答案是 0 。
提示：
1 <= words.length <= 10⁵
1 <= words[i].length <= 10⁵
words[i] 僅由小寫英文字母組成。
所有 words[i] 的長度之和不超過 5 * 10⁵ 。

分析

利用KMP 計算那些前綴等于后綴，然后在字典樹中查詢，此前綴（后綴）是否存在，如果存在根據編號查詢出現數量。
注意：前綴不能為空，可以等于本串。

代碼

核心代碼

template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:CTrieNode* AddChar(TData ele, int& iMaxID){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifconst int index = ele - cBegin;auto ptr = m_vPChilds[ele - cBegin];if (!ptr){m_vPChilds[index] = new CTrieNode();
#ifdef _DEBUGm_vPChilds[index]->m_iID = ++iMaxID;m_childForDebug[ele] = m_vPChilds[index];
#endif}return m_vPChilds[index];}CTrieNode* GetChild(TData ele)const{
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifreturn m_vPChilds[ele - cBegin];}
protected:
#ifdef _DEBUGint m_iID = -1;std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:int m_iLeafIndex = -1;
protected:CTrieNode* m_vPChilds[iTypeNum] = { nullptr };
};template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:int GetLeadCount(){return m_iLeafCount;}template<class IT>int Add(IT begin, IT end){auto pNode = &m_root;for (; begin != end; ++begin){pNode = pNode->AddChar(*begin, m_iMaxID);}if (-1 == pNode->m_iLeafIndex){pNode->m_iLeafIndex = m_iLeafCount++;}return pNode->m_iLeafIndex;}template<class IT>CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end){auto ptr = &m_root;for (; begin != end; ++begin){ptr = ptr->GetChild(begin);if (nullptr == ptr){return nullptr;}}return ptr;}CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:int m_iMaxID = 0;int m_iLeafCount = 0;
};class KMP
{
public:virtual int Find(const string& s, const string& t){CalLen(t);m_vSameLen.assign(s.length(), 0);for (int i1 = 0, j = 0; i1 < s.length(); ){for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);//i2 = i1 + j 此時s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等m_vSameLen[i1] = j;//t[0,j)的結尾索引是j-1，所以最長公共前綴為m_vLen[j-1]，簡寫為y 則t[0,y)等于t[j-y,j)等于s[i2-y,i2)if (0 == j){i1++;continue;}const int i2 = i1 + j;j = m_vLen[j - 1];i1 = i2 - j;//i2不變}for (int i = 0; i < m_vSameLen.size(); i++){//多余代碼是為了增加可測試性if (t.length() == m_vSameLen[i]){return i;}}return -1;}vector<int> m_vSameLen;//m_vSame[i]記錄 s[i...]和t[0...]最長公共前綴，增加可調試性static vector<int> Next(const string& s){const int len = s.length();vector<int> vNext(len, -1);for (int i = 1; i < len; i++){int next = vNext[i - 1];while ((-1 != next) && (s[next + 1] != s[i])){next = vNext[next];}vNext[i] = next + (s[next + 1] == s[i]);}return vNext;}
protected:void CalLen(const string& str){m_vLen.resize(str.length());for (int i = 1; i < str.length(); i++){int next = m_vLen[i - 1];while (str[next] != str[i]){if (0 == next){break;}next = m_vLen[next-1];}m_vLen[i] = next + (str[next] == str[i]);}}int m_c;vector<int> m_vLen;//m_vLen[i] 表示t[0,i]的最長公共前后綴	
};class Solution {
public:long long countPrefixSuffixPairs(vector<string>& words) {CTrie<> trie;unordered_map<int, int> mNoNum;long long llRet = 0;for (const auto& str : words){			KMP kmp;kmp.Find(str, str);queue<int> indexs;for (int i = str.length()-1; i >= 0 ; i--){if (kmp.m_vSameLen[i] == (str.length() - i)){indexs.emplace(str.length() - i);}}auto ptr = &trie.m_root;for (int i = 0; i < str.length(); i++){ptr = ptr->GetChild(str[i]);if (nullptr == ptr){break;}if ((-1 != ptr->m_iLeafIndex)&&indexs.size()&&( indexs.front()==i+1 )){llRet += mNoNum[ptr->m_iLeafIndex];					}while (indexs.size() && (indexs.front() == i + 1)){indexs.pop();}}mNoNum[trie.Add(str.begin(), str.end())]++;}return llRet;}
};

擴展閱讀

視頻課程

有效學習：明確的目標及時的反饋拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

我想對大家說的話
聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/710947.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/710947.shtml
英文地址，請注明出處：http://en.pswp.cn/news/710947.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！