帮别人做网站自己为什么会被抓,上海建设工程监理行业协会网站,用微信微博网站来做睡眠经济,网站建设中英文表述作者推荐
动态规划的时间复杂度优化
本文涉及知识点
字符串 字典树 KMP 前后缀
LeetCode:3045统计前后缀下标对 II
给你一个下标从 0 开始的字符串数组 words 。 定义一个 布尔 函数 isPrefixAndSuffix #xff0c;它接受两个字符串参数 str1 和 str2 #xff1a; 当 st…作者推荐
动态规划的时间复杂度优化
本文涉及知识点
字符串 字典树 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 105 1 words[i].length 105 words[i] 仅由小写英文字母组成。 所有 words[i] 的长度之和不超过 5 * 105 。
分析
利用KMP 计算那些前缀等于后缀然后在字典树中查询此前缀后缀是否存在如果存在根据编号查询出现数量。 注意前缀不能为空可以等于本串。
代码
核心代码
templateclass 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_mapTData, CTrieNode* m_childForDebug;
#endif
public:int m_iLeafIndex -1;
protected:CTrieNode* m_vPChilds[iTypeNum] { nullptr };
};templateclass TData char, int iTypeNum 26, TData cBegin a
class CTrie
{
public:int GetLeadCount(){return m_iLeafCount;}templateclass ITint 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;}templateclass ITCTrieNodeTData, 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;}CTrieNodeTData, 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;}vectorint m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀增加可调试性static vectorint Next(const string s){const int len s.length();vectorint 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;vectorint m_vLen;//m_vLen[i] 表示t[0,i]的最长公共前后缀
};class Solution {
public:long long countPrefixSuffixPairs(vectorstring words) {CTrie trie;unordered_mapint, int mNoNum;long long llRet 0;for (const auto str : words){ KMP kmp;kmp.Find(str, str);queueint 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()i1 )){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
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
