问题标签 [string-algorithm]

我实现了 jarowinkler算法。在那个算法中，我采用了字符串源和字符串目标。字符串目标作为输入字符串源作为数组，如 source[0]。如何将jarowinkler算法实现为数组列表输入？请看下面的代码

}

上面的代码是静态类，需要实现为该类的数组列表。数组列表必须按照 jaro winkler 算法进行比较。下面的代码我发布了我的主要课程。

所以我需要为这个代码实现数组列表，从arraylist中获取输入。将该列表拆分为单词。单词比较必须比较源和目标然后它给出匹配百分比。

给定一组 50k 个字符串，我需要找到所有对(s, t)、和都包含在这个集合中s。ts + t

我试过的

，还有一个额外的约束：s.length() >= 4 && t.length() >= 4. 这使得可以按长度为 4 的前缀和单独的后缀对字符串进行分组。然后对于每个composed长度至少为 8 的字符串，我查找s使用前四个字符的composed候选集和t使用其后四个字符的候选集。这可行，但它需要查看 3000 万个候选对(s, t)才能找到 7k 个结果。

如此多的候选者来自这样一个事实，即字符串是（主要是德语）来自有限词汇表的单词，并且单词的开头和结尾通常相同。它仍然比尝试所有 2.5G 对要好得多，但比我希望的要差得多。

我需要的

由于额外的约束可能会被删除并且集合会增长，我正在寻找更好的算法。

“失踪”的问题

有人抱怨我不问问题。所以缺少的问号在下一句的末尾。理想情况下，如何在不使用约束的情况下更有效地做到这一点？

在我的机器人中，我实现了一个关键字过滤器，机器人会在聊天中写入的每条消息中进行审查，直到现在它可以工作，但我想改进它，出于尊重的原因，我不会在这里放词，所以我会放其他一些例子，

机器人会检测你是否写了例如“vulgar”、“badword”、“hello”

但我想要实现的是检测他们是否写“hellooo”、“vuulgarr”、“vulg4rr”

这是我存储单词的基地：

坏词.js

这是我的函数，它检查是否有坏词出现，拆分任何单词，然后如果找到结果则删除消息，使用 indexOf()

index.js

有什么改进的办法吗，谢谢

我目前正在尝试确定给定数组（数字 1 到 n 的排列）是否是任何二进制字符串的后缀数组。

例如对于 n = 3，A = {2, 1, 3} 是有效的，因为存在 [01] < [1] < [101] 的二进制字符串 [101]（使用字典顺序）。但是 {2, 3, 1} 不是一个有效的后缀数组，因为不存在字典顺序适用的二进制字符串。

我目前的方法只是枚举长度为 n 的所有二进制字符串，并检查后缀数组是否按每个字符串正确排序。这显然相当慢，因为有 2^n 个候选二进制字符串要在 O(n) 中进行检查。

解决这类问题的明显方法是在有效的后缀数组中寻找相似之处，但是到目前为止我只能推断出一个属性：

如果 A 是二进制字符串的有效后缀数组，则在 A 前面加上 1 并递增 A 的所有值也会产生一个有效的后缀数组。

但是，在尝试验证它们时，此属性对不以 1 开头的后缀数组没有帮助。

我有一大堆短字符串和一个自定义距离函数（比如说 Damerau-Levenshtein 距离）。

问：根据自定义距离从池中获取前 N 个字符串的最先进的解决方案是什么？

我正在寻找解决这个问题的理论方法以及编码实现（Java、Python 等）。

给定一个 FASTA 文本文件 (Rosalind_gc.txt)，我应该检查每个 DNA 记录并确定鸟嘌呤-胞嘧啶 (GC) 含量的百分比 (%)。

这方面的例子是：

样本数据集：

样本输出：

罗莎琳德_0808 60.919540

所以基本上遍历每个字符串，计算 G/C 出现的次数，然后将总数除以每个字符串的长度。我的问题是学习如何识别代码中的中断（即 >Rosalind_6404 ）。我想要一个不使用 Biopython 和 biopython 方法的代码示例。

给定一个仅包含四个字母的字符串序列，['a','g','c','t'] 例如：agggcttttaaaatttaatttgggccc.

找到字符串序列中所有长度相等的最短唯一子串（长度应该是所有唯一子串中的最小值）？

例如：aaggcgccttt 答案：['aa', 'ag', 'gg','cg', 'cc','ct'] 解释：长度为 2 的最短唯一子串

我尝试使用后缀数组和最长公共前缀，但我无法完美地绘制解决方案。

我正在尝试用 Java 编写一个 madlibs 程序。有一种方法采用模板字符串、该字符串中所有占位符的 ArrayList 以及将替换这些模板的所有用户输入的 ArrayList 作为参数。

该方法如下所示：

问题是，该方法是用替换替换所有出现的给定模板，例如“[形容词]”，而不仅仅是第一个。我尝试template = template.replaceFirst(placeholders.get(i), replacements.get(i))改用，但它用所有用户输入替换了第一个占位符，并忽略了其余部分。

这是我使用的模板：

我知道占位符的 ArrayList 与模板中的占位符匹配，并且该 ArrayList 与用户输入的 ArrayList 长度相同。

我应该做些什么不同的事情？

假设我有一系列感兴趣的元素，其中A, B, C...散布着无关符号x。我想从预定义距离内发生的一组预定义有趣组合中识别元素包。符号跨度之间可能存在重叠。例如，在字符串中，如果最大距离为 5 C x x A A x x C，算法将检测到两倍的模式。A A C

例如说我的一组有趣的组合是：

我有一个序列：

并且最大跨度为5。

我的算法应该输出：

并且将无法识别模式A A C，因为感兴趣的元素之间的跨度大于 5。

我的直觉说这是某种动态编程，但也许它只是我无法发现的知名算法的一个实例。

关于方法/解决方案的任何提示？

假设我们一次旋转一个字符串（“abcd”->“bcda”）。经过 t 次旋转后，我们得到相同的字符串。设 t 是这样的最小旋转次数。

例如：

1. 对于 S = "aaaa"，t = 1
2. 对于 S = "abcabc"，t = 3
3. 对于 S = "abcdef"，t = 6

现在我的问题是，是否有任何字符串符合这个条件：t > len(S)/2 和 t < len(S)？如果不是，你能解释一下为什么吗？