string - 字符串匹配的随机算法

Question

问题:

给定文本 t[1...n, 1...n] 和 p[1...m, 1...m], n = 2m，来自字母表 [0, Sigma-1]，我们说 p 在 匹配 t >[i,j] 如果 t[i+k-1, j+L-1] = p[k,L] 对于所有 k,L。设计一种随机算法，以高概率在 O(n^2) 时间内找到所有匹配项。

图片:

谁能帮我理解这段文字的意思？我相信这是在说“t”中有两个词，模式也是两个词，但两个模式的长度都是“t”的一半。但是，从这里我不明白 [i,j] 的范围是如何发挥作用的。那个 if 语句让我难以理解。

这也可能是说 t 和 p 是二维数组，而您正在尝试从 t 二维数组中的模式匹配“框”。

如有任何帮助，我们将不胜感激，谢谢!

Answer 1

该问题要求您找到 2D 模式，即由 t 数组中的 p 数组定义，该数组也是 2D。

这个问题最明显的随机解决方案是生成两个随机索引 i 和 j 然后开始从 (i, j).

为避免进行冗余搜索，您可以跟踪您之前访问过的(i, j) 对，这可以使用简单的查找二维数组来完成。

上面的复杂度在最坏的情况下是O(n^3)。

---

您还可以使用散列 来比较字符串，以将复杂度降低到O(n^2)。

您首先需要逐行散列t 数组并将值存储在类似hastT 的数组中，您可以使用Rolling hash algorithm为此。

然后您可以使用滚动哈希算法对 p 数组进行哈希处理，并将哈希值逐行存储在数组 hashP 中。

然后在生成随机对(i, j)时，可以使用数组hashT得到对应t数组的hash > 在线性时间内而不是需要二次时间的暴力比较并进行比较(请注意，哈希中可能存在冲突，您可以在哈希完全匹配时进行暴力比较)。

要使用hashT 找到相应的散列，我们可以执行以下操作，假设当前对(i, j) 是(3, 4)，p 数组的维度是 2 x 3。

然后我们可以通过比较hashT[3][7] - hash[3][3] == hashP[3]来求出结果，以上逻辑来自rolling哈希算法。

使用哈希在线性时间内搜索的伪代码:

hashT[][], hashS[]

i = rand(), j = rand();

for(int k = i;k < i + lengthOfColumn(p);i++){
    if((hashT[i][j + lengthOfRow(p)] - hashT[i][j-1]) != hashP[i]){
        //patter does not match.
        return false;
    }
}