字符串匹配

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]的范围如何发挥作用。如果陈述覆盖我的头。

这也可能是说t和p是二维数组，您试图匹配t 2D数组中的模式的“框”。

任何帮助将不胜感激，谢谢！

Answer 1

该问题要求您找到2D pattern，即阵列在t阵列中定义，该阵列也是2D阵列。

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

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

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

---

您还可以使用hashing比较字符串的复杂性减少到O(n^2)。

您首先需要将t阵列逐行散列并将值存储在像hastT这样的数组中，您可以使用Rolling hash algorithm。

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

然后，当你生成随机对(i, j)，您可以使用线性时间，而不是蛮力对比的是需要二次的时间和比较阵列hashT得到相应的t阵列的哈希值（注意，可以在碰撞哈希可以蛮力当一个哈希匹配是完全可信的）。

要使用hashT我们可以做以下找到对应的散列，假设当前对(i, j)是(3, 4)，并且p阵列的尺寸是2 x 3。

然后我们可以比较hashT[3][7] - hash[3][3] == hashP[3]找到结果，上面的逻辑来自rolling hash algo。使用散列

为伪线性时间搜索：

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; 
    } 
}