顺序查找和蛮力字符串匹配

前一节蛮力法在排序问题上的两个应用。这里讨论该策略对查找问题的两个应用。第一个应用处理一个经典的问题，即如何在一个给定的列表中查找一个给定的值。第二个应用是处理字符串匹配问题。

顺序查找

该算法简单地将给定列表中的连续元素和给定的查找键作比较，直到遇到一个匹配的元素（成功查找），或者在遇到匹配元素前就遍历了整个列表（失败查找）。实现顺序查找的时候常常会使用一个小技巧：如果我们把查找键添加到列表的末尾，那么查找就一定会成功，所以不必在算法的每次循环时都检查是否到达了表的末尾。这里是伪代码，它的输入是用数组来实现的：

算法 SequentialSearch2(A[0..n], K)
    //顺序查找的算法实现，它用了查找键来做限位器
    //输入：一个n个元素的数组A和一个查找键K
    //输出：第一个值等于K的元素的位置，如果找不到这样的元素，返回-1
    A[n] <- K
    i <- 0
    while A[i] ≠ K do
        i <- i+1
    if i < n return i
    else return -1

如果已知给定数组是有序的，我们可以做另外一个简单的改进：在这种列表中，只要遇到一个大于或等于查找键的元素，查找就可以停止了。

顺序查找是阐述蛮力法的很好的工具，它有着蛮力法典型的优点（简单）和缺点（效率低）。无论是在最差情况还是平均情况下，该算法仍然是一个线性算法。

蛮力字符串匹配

字符串匹配问题：给定一个n个字符组成的串，称为文本,一个m个字符的串，称为模式，从文本中寻找匹配模式的子串。

将模式对准文本的前m个字符，然后从左到右匹配每一对相应的字符，直到m对字符串全部匹配。若遇到一对不匹配的字符，模式向右移动一位，然后从模式的第一个字符开始，继续把模式和文本中的对应字符进行比较。请注意，在文本中，最后一轮子串匹配的起始位置是n-m（假设文本位置的下标是从0到n-1）。因此，在这个位置之后，该算法就没有必要再作比较了。

算法 BruteForceStringMatch(T[0..n-1], P[0..m-1])
    //该算法实现了蛮力字符串匹配
    //输入：一个n个字符的数组T[0..n-1]代表一段文本
    //      一个m个字符的数组P[0..m-1]代表一个模式
    //输出：如果查找成功的话，返回文本的第一个匹配子串中第一个字符的位置
    //      否则返回-1
    for i <- 0 to n-m do
        j <- 0
        while j < m and p[j]=T[i+j] do
            j  <- j + 1
        if j = m return i
    return -1

最坏的情况是，算法可能会做足m次比较。在这种情况下，该算法属于Θ(nm)。然而，事实上，大多数移动都发生在很少几次比较之后，因此，该算法的平均是效率比最差效率好得多。在查找随机文本的时候，它能够显示出线性效率——Θ(n+m)=Θ(n).

Loading Disqus comments...
Table of Contents