文章目录 后缀树 后缀数组 概念 sa[] rk[] height[] 例题 HDU-1403最长公共子串 洛谷P2408 不同子串个数 HDU-5769Substring 后缀树 建议先了解一下字典树...后缀树(suffix tree)就是把所有的后缀子串用字典树的方法建立的一棵树，如图： 其中根节点为空，还可以在叶子节点后用一个’$'符标识结束，从根节点出发就能到达所有的子串情况。...后缀数组和后缀自动机可以看作是对后缀树时间和空间上的优化，通过映射关系避免建树和提高树节点重复利用率。...后缀数组 概念 直接对后缀树构造和编程不太方便，而后缀数组(suffix array)就是更简单的替代方法。...，和最长公共前缀(Longest Common Prefix，LCP)相关。
当时，没有后缀数组 今天将是，事实上，自己的后缀阵列组合rmq或到，但是，题意理解的一个问题，再折腾了很长时间，，，， 此处简单解释下题目例子吧，希望对读者有帮助 以最后一组数据为例 myxophytamyxopodnabnabbednabbingnabit...6 0 9 9 16 16 19 19 25 25 32 32 37 前两行不解释，题目叙述非常清楚 从第三行，0 9 指的是第一个字符串是从第一行的字符串的0-9 左闭右开， 下面5行同样 继续看题目的正文叙述的例子...s[i]:-1; } for(k=1;k从1開始，由于0*2=0*/ { sort(sa,sa+...lastlen=r-l; } printf("%I64d %I64d\n",ansb,ansa); } return 0; } 再加一个rmq+后缀数组求最长公共前缀的模板吧...s[i]:-1; } for(k=1;k从1開始。
题目 给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。...如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。 请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。...只有一种让剩余数组成为平衡数组的方案。 示例 2： 输入：nums = [1,1,1] 输出：3 解释：你可以删除任意元素，剩余数组都是平衡数组。...示例 3： 输入：nums = [1,2,3] 输出：0 解释：不管删除哪个元素，剩下数组都不是平衡数组。...解题 正反双向的奇偶前缀和都求出来 删除某个元素后，逆向的奇偶后缀和需要交换 class Solution { public: int waysToMakeFair(vector& nums
从字符串的大小比较定义来看，S的开头两个位置后缀u和v进行比较的结果不可能是相等，因为u=v的必要条件len(u)=len(v)是不可能满足的。 ...简单地说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。容易看出后缀数组和名次数组互为逆运算。...下面仅介绍倍增法构造后缀数组 最直接的方法，当然是把S的后缀都看作一些普通的字符串，按照一般字符串排序的方法对它们从小到大进行排序。 ...倍增算法正是充分利用了各个后缀之间的联系，将构造后缀数组的数组的最坏时间复杂度成功降到O(nlogn)。 对于一个字符串u，我们定义u的k－前缀 ? ...LCPi(I,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。
30 for (i = 0; i < n; i++) b[ct[s[a[i]]]++] = a[i]; 31 } 32 33 /* 34 倍增算法,构造后缀数组的最坏时间复杂度为...35 参数： 36 int *r：待排序的字符串放在 r 数组中 ， 从 r[0] 到 r[n-1] ， 长度为 n ， 且最大值小于 m 。...38 int *sa：函数结束后，结果放在 sa 数组中，从 sa[0] 到 sa[n-1] 。...113 容易看出，后缀数组和名次数组为互逆运算。 114 设字符串的长度为 n 。...LCP(i,j)也就是后缀数组中第i个 129 和第j个后缀的最长公共前缀的长度。
挑战程序竞赛系列（71）：4.7高度数组（1） 传送门：POJ 2217: Secretary 题意： 给定两个字符串S和T。请计算两个字符串最长的公共字符串子串的长度。...LCP概念：在后缀数组中相邻两个后缀的最长公共前缀（Longest Common Prefix） ?...for (int i = 0; i 后缀的当前排名 int h = 0;...for (int i = 0; i < n; ++i) { int j = sa[rank[i] - 1]; // 后缀i的前一个后缀 if...= cs[i + h]) break; } lcp[rank[i] -1] = h; } }
例题15 UVa11468 Substring AC自动机上的算法 例题16 UVa11019 Matrix Matcher 二维匹配；AC自动机 例题17 UVa11107 Life Forms 后缀数组...+height数组 例题18 LA4513 Stammering Aliens LCP；hash函数 习题 UVa11488 Hyper Prefix Sets Trie的应用 LA5913 Dictionary...，求不含它们的最长串 LA4126 Password Suspects 字符串的动态规划 UVa10829 L-Gap Substrings 后缀数组 LA3490 Generator 自动机；数学期望...例题21 UVa11922 Permutation Transformer 伸展树；和分裂合并的序列 例题22 UVa11996 Jewel Magic 字符串；Hash函数；伸展树 习题 LA4847...Binary Search Tree 和BST有关的计数问题 LA5705 Very Boring Homework BST快速模拟；递归。
[MAX_N + 1]; // sa[i] := 字典序为i的后缀的起始下标；lcp[i] := S[sa[i]...]与S[sa[i+1]...]的最长公共前缀长度 int rank[MAX_N +...1], tmp[MAX_N + 1]; // 比较(rank[i], rank[i+k])和(rank[j], rank[j+k]) bool compare_sa(const int i, const...rank[j + k] : -1); } // 计算字符串S的后缀数组 void construct_sa() { // 初始长度为1，rank直接取字符的编码 for (int i...[i] < K) { top = contribution = 0; } else {// s1的后缀与s2的后缀的最长公共前缀大于...k int size = 0; // 满足条件的s1后缀个数 if ((is_s1 && sa[i] < l1) || (!
注意到后缀转化后的数组同原串转化后的数组最多只会相差 10 位（每种字符第一次出现的位置有差异）。 于是我们以这 10 个位置为关键点，分段进行比较。...所以我们先对原串转化成的数组建立后缀数组，这样一来若要求解两个后缀转化成的数组的 \text{LCP}，就可以直接 按关键点划分成若干段，将每一部分依次比较。...既然能够求出 \text{LCP}，那么只要比较 \text{LCP} 的后一位就能比较两个不同后缀转化成的数组的字典序，也就可以将所有后缀转化成的数组做一遍排序。...然后，预先求出排名相邻的后缀的 \text{LCP}（类似于一般后缀数组中的 Height 数组）。 询问时在这个 “Height 数组” 上分别向左向右二分一下即可。...发现其实也并不需要使用后缀数组，求 \text{LCP} 直接 Hash+二分 也行，就是复杂度上多了只 \log。 Code /* 超！还卡哈希！
用go语言，给定两个字符串数组 wordsContainer 和 wordsQuery，要对每个 wordsQuery[i] 找到一个与其有最长公共后缀的字符串。...对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。...• 对于每个查询字符串，初始化当前最长公共后缀的长度 (maxLen) 为0，和对应的字符串索引 (bestIndex)。...• 从当前查询字符串的尾部开始向前检查与当前 wordsContainer[j] 的后缀匹配。 • 计算两个字符串，从尾部开始的最大匹配长度。...• 若发现新的公共后缀长度大于 maxLen，则更新 maxLen 和 bestIndex 为当前字符串的索引。
挑战程序竞赛系列（72）：4.7高度数组（2） 传送门：POJ 3415: Common Substrings 题意： 公共子串：统计A和B长度不小于K的公共子串个数。...思路： 一开始想当然的求LCP数组，把LCP遍历一遍，大于K的，ans不断累加ans += lcp[i] - k + 1，但这只是一部分解，因为所求的只是相邻后缀的最长公共前缀。...一种直观的做法时，两个for循环，对于当前位置属于S的LCP时，向下找属于T的后缀，把每个后缀的最长对应公共前缀加一遍，但TLE了，此处需要利用单调性来简化时间复杂度。采用记忆化手段，用栈。...此处代码参考hankcs的代码，具体思路如下：对应于S的lcp，先不管三七二十一，贡献值都以最大的加，但我们知道，中间如果lcp变小，意味着后缀的公共前缀在不断减小，此时需要按照最小的算，只需要在贡献值上...针对T的lcp，同样处理。
这样一来我们查询和插入可以一起完成（重点体会这个查询和插入是如何一起完成的，稍后，下文具体解释），所用时间仅仅为单词长度，在这一个样例，便是10。...图3 逐步构造后缀树 3.4、初窥门径 加入一个新的前缀需要访问树中已有的后缀. 我们从最长的一个后缀开始(图3中的BAN), 一直访问到最短的后缀(空后缀)....那么要构造下一个前缀BOOKK的后缀树的话, 只需要访问树中已存在的每一个后缀, 然后在它们的末尾加上K. 前4个后缀BOOK, OOK, OK和K都在叶节点上结束....图8 加上后缀指针(虚线)的ABABABC的后缀树 介绍一下如何创建后缀指针. 后缀指针的创建是跟后缀树的更新同步的. 随着我们从激活节点移动到结束节点, 我把每个新的叶节点的父亲的路径保存下来....；后缀数组和后缀树都是与字符串的后缀集合有关的数据结构；trie图中的后缀指针和后缀树中的后缀链接这两个概念及其一致。
题意 题目链接 Sol 这题打死我也不会想到后缀数组的，应该会全程想AC自动机之类的吧 但知道这题能用后缀数组做之后应该就不是那么难了 首先把\(S\)和\(S0\)拼到一起跑，求出Height数组 暴力枚举每个后缀是否能成为答案...具体来说，每次比较当前后缀和\(S_0\)的lcp，如果长度\(< N\)的话就从不合法的位置继续匹配 rmq维护一下区间lcp最小值 BZOJ上被完美卡常 // luogu-judger-enable-o2
我们用子问题的解 lcpLeft 与 lcpRight 构造原问题的解 LCP(S_i \cdots S_j)LCP(Si⋯Sj)。...在字典树中，从根向下的每一个节点都代表一些键值的公共前缀。 但是我们需要找到字符串q 和所有键值字符串的最长公共前缀。...因为最长公共前缀不可能比某个字符串本身长 算法 最后的问题就是如何找到字典树中满足上述所有要求的最深节点。...我们从根节点遍历这颗字典树，直到因为不能满足某个条件而不能再遍历为止。 图 4....时间复杂度：预处理过程 O(S)O(S)，其中 SS 数组里所有字符串中字符数量的总和，最长公共前缀查询操作的复杂度为 O(m)O(m)。 建立字典树的时间复杂度为 O(S)O(S)。
Tag : 「字符串哈希」、「二分」、「后缀数组」 给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的连续子串，在 s 中出现 次或更多次。这些出现之间可能存在重叠。...二分范围为 ，关键在于如何 check 函数，即实现「检查某个长度 作为最大长度，是否存在合法方案」。...；二分最大长度的复杂度为 ；整体复杂度为 空间复杂度： 后缀数组 另外一个较为进阶的做法是使用「后缀数组」，后缀数组有基于基数排序的倍增实现，复杂度为 ，也有基于 DC3 的...后缀数组包含几个核心数组： sa 数组：字典序排名为 的后缀是第几个； rk 数组：第 个后缀的排名是多少（不难发现 rk 与 sa 满足 ）； height 数组：存储 与...的 LCP（最长公共前缀） 为何值。
挑战程序竞赛系列（73）：4.7高度数组（3） 传送门：POJ 3729: Facer’s String 题意： 公共子串： 给出两个字符串A,B,求满足下列条件的C的个数: 1....思路： 求出A中存在多少后缀，使得其和B的前缀长度大于等于k，再求出A中存在多少后缀，使得其和B的前缀长度等于k+1，最后两式相减。...所以在>=k的范围内，存在一个B，就可以统计A的后缀个数了，若没有B，则统计也没用。...new Integer[n + 1]; rank = new int[n + 1]; tmp = new int[n + 1]; lcp...= arra[j + h]) break; } lcp[rank[i] - 1] = h;
答案2023-04-17： # 大体过程如下： 1.首先定义一个 Trie 树的结点类型 TrieNode，包含 nexts 数组和 indies 切片，其中 nexts 数组用于存储子节点，indies...3.实现 Constructor 方法，接受一个字符串数组作为参数，初始化 WordFilter 对象。在该方法内部，遍历单词数组，将每个单词插入正序和倒序的 Trie 树中。...4.实现 F 方法，接受两个字符串作为前缀和后缀参数，查找并返回满足要求的单词在原单词数组中的下标。该方法内部，分别在正序和倒序 Trie 树上匹配前缀和后缀，获取包含相应前缀和后缀的单词的下标集合。...- 查找函数 `F` 的时间复杂度为 O(M \log N)，其中 M 是相应前缀和后缀所匹配到的下标集合的大小，N 是单词数组的长度。...# 空间复杂度： - 构造函数 `Constructor` 的空间复杂度为 O(NL^2)，即正序和倒序两棵 Trie 树的总节点数。
分析 方法一：遍历后缀，hash检索 我们将数据存放在一个容器中，然后逐个拿出，检测拿出的字符串是否存在后缀在原容器中，如果存在，则删除，不存在则继续查看更小后缀，直至对比完该字符串，转而从容器拿出下一个元素...实现 Trie (前缀树)[2] 假设我们现在给定字符串数组："A", "to", "tea", "ted", "ten", "i", "in", "inn" ? 这颗树怎么理解呢？...根节点无内容，读取第一个元素 A 加入这颗树，结果为：{A: {}}，读取第二个字符串 to ，构造出 {t:{o:{}}, A:{}}，继续读取第三个元素，构造出：{t:{o:{}, e: {a: {...的作用是一样的，区别在于传入参数的不同；2.第一个参数都是，指定函数体内this的指向；3.第二个参数不同，apply是传入带下标的集合，数组或者类数组，apply把它传给函数作为参数。...call从第二个开始传入的参数是不固定的，都会传给函数作为参数。
答案2023-04-17：大体过程如下：1.首先定义一个 Trie 树的结点类型 TrieNode，包含 nexts 数组和 indies 切片，其中 nexts 数组用于存储子节点，indies 切片用于存储当前节点对应的单词在原单词数组中的下标...3.实现 Constructor 方法，接受一个字符串数组作为参数，初始化 WordFilter 对象。在该方法内部，遍历单词数组，将每个单词插入正序和倒序的 Trie 树中。...4.实现 F 方法，接受两个字符串作为前缀和后缀参数，查找并返回满足要求的单词在原单词数组中的下标。该方法内部，分别在正序和倒序 Trie 树上匹配前缀和后缀，获取包含相应前缀和后缀的单词的下标集合。...查找函数 F 的时间复杂度为 $O(M \log N)$，其中 $M$ 是相应前缀和后缀所匹配到的下标集合的大小，$N$ 是单词数组的长度。...空间复杂度：构造函数 Constructor 的空间复杂度为 $O(NL^2)$，即正序和倒序两棵 Trie 树的总节点数。
即让绿色部分的前缀和后缀相同且尽量长。...image-20210809103144669.png 好了，现在我们已经找到优化匹配过程的方法了，就剩下一个问题：如何求得 P 串的某个前缀子串的最长的相同的前缀和后缀的长度（有点拗口，多读几遍理解...[3] = 1,因为0到2的串为aba，最长相等的前缀和后缀为“a” 2.3.2 怎么求next数组？...明确next数组的定义后，思考如何求解next数组。...AC自动机算法和KMP很像，一共分为三步：构造一棵 Trie 树，构造失败指针和模式匹配过程。
云服务器
ICP备案
云直播
腾讯会议
对象存储
