朋友圈

字典树

什么是字典树字典树(Trie Tree) 是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。它的优点是：利用字符串的公共前缀来减少查询时间，最大...

什么是字典树字典树(Trie Tree) 是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。——百度 · 百科它是一种高效存储和查找字符串集合的树形结构，核心思想是利用公共前缀共享路径，从而减少重复比较，实现快速的前缀匹配与检索。实现可以定义字典树的结构如下：struct trie { bool end = 0; //是否以当前字母结尾 int count=0; //公共前缀的数量 unordered_map ch; //子树 };添加void add(trie &tr,string s){ tr.count++; if(s.length()==0){ tr.end=1; return; } add(tr.ch[s[0]],s.substr(1)); }前缀数量查找ll ask(trie &tr,string s){ if(s.length()==0){ return tr.count; } if(tr.ch.count(s[0])){

马拉车算法

简介Manacher算法，又叫“马拉车”，它可以在时间复杂度和空间复杂度都是O(n)的情况下，求出一个字符串的最长回文串长度。回文串常规解法以每一个点为中心对称点，每次保留最长回文子串的长度，最...

Young143 Blog

马拉车算法

简介Manacher算法，又叫“马拉车”，它可以在时间复杂度和空间复杂度都是O(n)的情况下，求出一个字符串的最长回文串长度。回文串常规解法以每一个点为中心对称点，每次保留最长回文子串的长度，最后得到的就是最长回文子串的长度，但是这样的时间复杂度为O（n^2），并且奇偶回文串是不一样的，奇数的情况下可以遍历每个字符进行中心扩散，偶数的情况下需要遍历每个间隔进行中心扩散。马拉车预处理字符串对于奇偶字符串的处理，manacher采用的是填充特殊字符的方法，并且在字符串两端都加入不同的字符，防止越界（因为不同字符一定不是回文串），比如字符串“abbccbba”，增加字符后变成“^#a#b#b#c#c#b#b#a#$”.核心算法重新定义字符串后就是马拉车的核心算法:在遍历新的字符串之前首先定义两个变量：c，r分别是在已遍历的字符串中最长的一个回文串的中心位置，和他的右边界的位置。用一个数组p来记录每个位置的为中心的最远扩散距离，这个正好也是对应原串中的回文串长度。在遍历的过程中，首先判断当前位置是否在r之前，如果在的话可以根据回文串强对称性，可以把当前位置的数组p的值继承他对称的位置的值，继承

马拉车算法