字符串匹配算法

gaunthan Posted on Mar 31 2017

? Algorithm ?

> 给定一个 $n$ 个字符组成的串（称为文本(text)）、一个 $m (m \le n)$ 个字符的串（称为模式(pattern)），从文本中寻找匹配模式的字串。这就是字符串匹配问题。

## 蛮力字符串匹配
字符串匹配算法的蛮力实现是显而易见的：将模式对准文本的前 m 个字符，然后从左到右匹配每一对相应的字符，直到 m 对字符全部匹配（这时候找到了结果，算法可以停止了）或者遇到一对阿布匹配的字符。在后一种情况下，我们将模式右移一个位置，然后从模式的第一个字符开始，继续上述过程。

注意，在文本中，最后一轮子串匹配的起始位置是 $n-m$ （如果下标是从 0 到 n-1）。在这个位置以后，再也没有足够的字符可以匹配整个模式了，因此，算法也就没有必要再做比较了。

### 示意
下图是一个使用蛮力字符串匹配算法的例子：
![](https://leanote.com/api/file/getImage?fileId=58e19c91ab64413a33006f29)

### 实现
算法实现如下：
```c
int BruteForceStringMatch(const char * const text, 
					const char *const pattern)
{
    if(!text || !pattern) return -1;
    
    const int n = strlen(text), m = strlen(pattern);
    for(int i = 0; i != n - m; ++i) {
		int j = 0;
        while(j != m && text[i + j] == pattern[j]) {
			++j;
		}
        if(j == m) return i;
    }
    return -1;
}
```

### 效率分析
假设文本没有要查找的子串，而且每一次不匹配都发生在模式的最后一个字符上，即 $n-m+1$ 次尝试都会进行 m 次比较。因此，最坏情况下的时间复杂度为 $O(mn)$。然而，对于在自然语言文本中查找词的典型问题，可以认为大多数移动都发生爱很少几次比较之后。所以，该算法的平均效率应该比最差效率好得多。事实也是这样：在查找随机文本时，它能够显示出线性的效率，即 $\theta(n)$。

## 使用输入增强技术
蛮力字符串匹配算法在匹配过程中，若遇到不匹配，则会将模式右移一位。然而，有时候我们起始可以移动不止一位。通过对模式进程预处理已得到它的一些信息，把这些信息存储在表中，然后在给定文本中实际查找模式时使用这些信息。使用输入增强技术的字符串匹配算法有 Knuth-Morris-Pratt(简称KMP) 算法和 Boyer-Moore 算法。

这两种算法的主要区别在于它们如何对模式和文本中的相应字符进行比较：KMP 是从左向右比较，而 Boyer-Moore 算法从右到左比较。

虽然 Boyer-Moore 算法的基本思想很简单，但它的实现比较复杂。因此，我们可以从 R.Horspool 建议的 Boyer-Moore 算法的简化版本开始我们的讨论。Horspool 算法不仅更简单，而且在处理随机串的时候，效率并不一定比 Boyer-Moore 算法低。

## Horspool 算法

（未完待续）