在大数据集中查找最长公共子串
在过去的几天里，我进行了大量研究，读了很多东西，现在比以前更加困惑了。如何在一个大数据集中找到最长的公共子字符串？这个算法需要连续运行，以从该数据集中删除重复内容（长度各不相同）。所谓大数据集是指大约100MB的文本。 后缀树？后缀数组？Rabin-Karp算法？哪种方法最好？是否有可以帮助...
Kasai算法构建LCP数组的实际示例
我正在尝试完成Coursera上的字符串算法课程，并且在构建LCP数组的方法上遇到了困难，该方法在此视频中描述：https://www.coursera.org/learn/algorithms-on-strings/lecture/HyUlH/computing-the-lcp-array ...
如何从后缀树的子串中获取最长重复字符串
我需要找到子串中最长的重复字符串。比如说，我有字符串"bannana"。 维基百科says以下内容： 在计算机科学中，最长重复子串问题是查找至少出现两次的字符串的最长子串的问题。在带有字符串“ATCGATCGA $”的图中，最长的重复子串是“ATCGA”。 因此，我认为对于字符串"ban...
在一个字符串中查找所有重复的子串以及它们出现的次数。
问题： 我需要找到满足以下条件的所有字符序列： 字符序列必须出现超过一次（因此 (LE, 1) 不符合要求）。 字符序列必须长于一个字符（因此 (M, 2) 不符合要求）。 字符序列不能是已存在的更长序列的一部分，而该更长序列出现相同次数（如果存在 (LIO, 2)，则 (LI, 2) ...
有没有可能在O(n)的时间内计算一个字符串中不同子串的数量？
给定一个长度为 n 的字符串 s，是否有可能在 O(n) 的时间复杂度下计算 s 中不同子串的数量？ 示例： 输入：abb 输出：5（'abb'、'ab'、'bb'、'a'、'b'） 我已经进行了一些研究，但似乎找不到一种解决这个问题的高效算法。我知道 O(n^2) 的方法是可行的，但...
连续添加字符以获得字典中最长的单词
给定一个单词字典和一个初始字符，找到通过连续添加字符而可能得到的最长单词。在任何给定的情况下，该单词应为字典中的有效单词。 例如：a -> at -> cat -> cart -> chart ...
如何使用 Trie 数据结构来查找所有可能子字符串的 LCP（最长公共前缀）和？
问题描述： 参考文献：与字符串玩耍 根据问题描述，寻找给定字符串所有可能子字符串的公共前缀长度之和的一种朴素方法是： #include <cstring> #include <iostream> using std::cout; using std::cin; ...
给定一个字符串，找出其中所有在字典中的排列组合。
这是一道面试题： 给定一个字符串，找出所有在字典中的排列组合。 我的解决方案： 将字典中的所有单词放入后缀树中，然后在树中搜索字符串的每个排列组合。 搜索时间为 O(n)，其中 n 是字符串的大小。但是该字符串可能有 n! 种排列组合。 如何提高效率？