问题标签 [string-algorithm]

（这个问题与音乐无关，但我以音乐为例。）

在音乐中，构造乐句的一种常见方式是作为一系列音符，其中中间部分重复一次或多次。因此，该短语由引言、循环部分和结尾部分组成。这是一个例子：

我们可以“看到”前奏是[EEE]，重复部分是[FGA F]，结尾是[CD]。所以拆分列表的方法是

其中第一项是前奏，第二项是重复部分重复的次数，第三部分是结尾。

我需要一种算法来执行这样的拆分。

但有一个警告是，可能有多种方式来拆分列表。例如，上面的列表可以拆分为：

但这是一个更糟糕的拆分，因为前奏和后奏更长。所以算法的标准是找到最大化循环部分的长度和最小化intro和outro的组合长度的分割。这意味着正确的拆分为

是

因为 intro 和 outro 的总长度是 2，而循环部分的长度是 9。

此外，虽然 intro 和 outro 可以为空，但只允许“真实”重复。因此，将不允许以下拆分：

将其视为为序列找到最佳“压缩”。请注意，某些序列中可能没有任何重复：

对于这些退化的情况，任何合理的结果都是允许的。

这是我的算法实现：

我不确定它是否正确，但它通过了我描述的简单测试。它的问题在于它的速度很慢。我查看了后缀树，但它们似乎不适合我的用例，因为我所追求的子字符串应该不重叠且相邻。

我有一个家庭作业问题，我试图解决好几个小时都没有成功，也许有人可以指导我正确思考它。

问题：

给定两个字符串 S1 和 S2，找到它们与间隙的最佳全局对齐的分数。差距成本由通用函数-() 给出。众所周知，对于间隙长度 - ≥ ， () 等于常数 C。

space O(min{|S1|,|S2|}*d)建议一种算法解决问题time O(|S1|*|S2|*d).

说明：在每个矩阵条目选择最佳间隙长度时，分别处理长度小于 d 的间隙和较长的间隙。除了常规最优值之外，在每个矩阵条目中存储通过使用较长间隙获得的最优值。

现在我们学习了以下两种算法：

与我们对成本函数一无所知的差距对齐：

与仿射间隙成本函数对齐

我的解决方案：

我知道我必须使用 d-rows 表才能满足空间要求，并使用这两种方法，但我很难将它组合成一个递归公式，这是我到目前为止所做的：

但是我不确定如何包括延长比 d 长的现有间隙的成本，甚至不确定如何检查我的递归公式是否正确。任何帮助，将不胜感激！

Longest Common Subsequence (LCS)问题是：给定两个序列A和，找到在和 中B都找到的最长子序列。例如，给定和，最长公共子序列是。ABA = "peterparker"B = "spiderman""pera"

有人可以解释这个Longest Common Subsequence算法吗？

所写的算法找到 的长度longest common subsequence，但可以修改以找到longest common subsequence完全的长度。

当我在 leetcode link上寻找一个等效问题的最快 python 解决方案时，我发现了这个算法。该算法是该问题最快的 Python 解决方案（40 毫秒），而且它似乎也具有时间复杂度，这比大多数其他解决方案O(m log m)的时间复杂度要好得多。O(m*n)

我不完全理解它为什么会起作用，并尝试到处寻找已知算法来Longest Common Subsequence解决问题以找到其他提及它的地方，但找不到类似的东西。我能找到的最接近的是Hunt–Szymanski algorithm 链接，据说O(m log m)在实践中也有，但似乎不是相同的算法。

我的理解是：

1. indeces_a被反转，以便在iAsfor 循环中保留较小的索引（这在执行下面的演练时更加明显。）
2. 据我所知，iAsfor 循环找到了longest increasing subsequenceof indeces_A_filtered。

谢谢！

A = "peterparker"这是算法的演练，例如B = "spiderman"

有人可以建议我如何制作在模式文本中包含“空白字母”的 Knuth–Morris–Pratt 算法吗？在输入时，您会得到模式和文本，模式在哪里？字符可以代表每一个字母。

我在解决

https://www.spoj.com/problems/BEADS/

SPOJ 的上述问题。我在下面陈述了相关信息：

问题陈述：项链的描述是一个字符串 A = a1a2 ... am 指定特定珠子的大小，其中最后一个字符 am 被认为以循环方式在字符 a1 之前。当且仅当字符串 aiai+1 ... ana1 ... ai-1 在词典上小于字符串 ajaj+1 ... ana1 ... aj 时，才说不相交点 i 比不相交点 j 差-1。字符串 a1a2 ... an 在字典上小于字符串 b1b2 ... bn 当且仅当存在整数 i，i <= n，因此 aj=bj，对于每个 j，1 <= j < i 和 ai <双。

输出：对于每个测试用例，只打印一行只包含一个整数 - 珠子的编号，它是最坏可能不相交时的第一个，即这样的 i，字符串 A[i] 在所有可能的 n 中按字典顺序最小项链脱节。如果有多个解决方案，则打印具有最低 i 的解决方案。

现在解决方案是使用 SUFFIX ARRAY。输入字符串 s，并与自身连接， s'=s+s ，因为我必须对数组的循环后缀进行排序。然后在s'上创建一个后缀数组，输出指向原始s的后缀的最小索引，即index < len(s)。

但是我面临一个问题。我在附加 '$' 字符以获得 SA，但我得到了错误的答案。在网上查找后，我找到了 1 个将“}”附加到字符串的解决方案。我发现 ascii('$') < ascii('a') < ascii('z') < ascii('}')

但我不明白这将如何产生影响，为什么这是被接受的答案并且还没有发现这会产生影响的案例。解决方案（AC）可以在这里找到：

链接到代码

PS.：我发现 SA 构造代码是正确的，唯一的问题是最后一个字符附加。通常我们在 SA 构造中附加“$”。

我正在尝试在 Javasacript 中提取 JPA 命名参数。这是我能想到的算法

我受到 https://stackoverflow.com/a/11324894/12924700中的解决方案的启发， 以过滤掉所有用单引号/双引号括起来的字符。

虽然上面的代码实现了上面的 3 个用例。但是当用户输入

我确实访问了 hibernate 的源代码，看看如何在那里提取命名参数，但我找不到正在做这项工作的算法。请帮忙。

（来自：https ://math.mit.edu/classes/18.417/Slides/alignment.pdf ）

第 11 页的幻灯片讨论了编辑距离和对齐距离如何等效。

我了解如何证明编辑距离将始终小于或等于相应的对齐距离。我们总是可以从给出相同结果的给定比对构造一系列编辑。由于编辑距离序列尽可能短，因此相应的序列至少也一样长。

我不明白如何证明反向不等式。任何人都可以提供证据吗？显然需要用三角不等式来证明。

同样，是否有任何资源可以严格处理该主题？例如，我想要证明为什么这两个距离满足度量空间的公理。