首先,看一个问题:(给定两个字符串,s 和 p,判断是否 p 是 s 的子串,如果是,则返回 p 在 s 中匹配的第一个位置)

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “hello”, needle = “ll”
Output: 2

Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1

这道题初步看来并没有什么难度,总共两个循环(s循环:选择每一个 s 中的字符;和p循环:匹配每一个 p 串中的字符)。

先循环选择 s 中的每个字符,如果 s 中的一个字符(位置i),与 p 的第一个字符相等,就开始 p 循环,往后比较s[i…] 和p[0…n],如果 p 中每一个字符都匹配完,匹配成功,然后返回 (i-j+1) 的值就可以了,因为此时 i 达到的位置是开始匹配 p 时,i 的位置往后移动 p 的长度。假如在p 循环中,如果遇到一个字符不匹配,我们就跳出查看字符串 p 的循环,在 s 串中继续选择下一个。当然,s 循环和 p 循环可以实现在一块(但是复杂度还是O(nm)O(nm),其中nnmm分别为 s 和 p 的长度):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int strStr(string haystack, string needle) {
int hsz = (int)haystack.size();
int nsz = (int)needle.size();
if (nsz == 0)
return 0;
int j= 0;
for (j = 0; i < haystack.size(); i++) {
if (haystack[i] == needle[j])
j++;
else {
i -= j; // go back
j = 0;
}
if (j == nsz)
return i - j + 1;
}
return -1;
}

这个算法相貌平平,没什么出众的地方,因为每次在 p 循环中匹配不成功(假设已经匹配 k 个字符),我们都要在 s 循环中跳回 k 个长度。

假如给两个以下的字符串:

s: dooxxooaaa

p: ooxxoob

i 0 1 2 3 4 5 6 7
d o o x x o o a
j 0 1 2 3 4 5 6
o o x x o o b

当匹配s[7]和p[6]时,结果是不匹配,这时候,如果按照之前的算法,我们将 i 移到 2, 继续然后继续比较s[2…], p[0…6]。但是,我们发现s[5],s[6]分别与p[0],p[1]是相等的,相等的原因是p的前缀ooxxoo是对称的,在s中也有这样一个对称的子串,我们只需要将 i 移动一定的步数,就可以节省很多时间,这个移动的长度就是对称前缀对称部分的长度。

计算数组

Pi 表示字符串 p 的前 i 个字符组成的前缀, next[i]的值(假如为j)表示Pi中的开始 j 个字符和末尾 j 个字符是一样的,而且对于前缀Pi来说,这样的 j 是最大值。next[i] = j的另外一个定义是:有一个含有 j 个字符的串,它既是 Pi 的真前缀,又是Pi 的真后缀

规定:next[1] = next[0] = 0

next[i]就是前缀数组,下面通过1个例子来看如何构造前缀数组。

例子1:caccab有5个前缀,求出其对应的next数组。

前缀2为ca,显然首尾没有相同的字符,next[2] = 0;

前缀3为cac,显然首尾有共同的字符c,故next[3] = 1;

前缀4为cacc,首尾有共同的字符c,故next[4] = 1;

前缀5为cacca,首尾有共同的字符ca,故next[5] = 2;

前缀6为caccab,首尾有没有的字符,故next[6] = 0;

如果仔细观察,可以发现构造next[i]的时候,可以利用next[i-1]的结果。假设模式已求得next[10] = 3,如:

000#xxx000#… 前缀P10

000 末尾3个字符

根据前缀函数的定义:next[10] = 3意味着末尾3个字符和P10的前3个字符是一样的
为求next[11],可以直接比较第4个字符和第11个字符.

  1. 如果它们相等,则 next[11] = next[10]+1 = 4,这是因为next[10] = 3保证了前缀P11和末尾4个字符的前3个字符是一样的.

000#xxx000#… 前缀P11

000# 末尾4个字符

所以只需验证第4个字符和第11个字符。

000#xxx000@… 前缀P11

000# 末尾4个字符

但如果这两个字符不相等呢?那就继续迭代,利用next[next[10]] = next[3]的值来求 next[11]。代码如下:

1
2
3
4
5
6
7
8
9
10
11
void compute_prefix(int next[], string p)  {   
int n = p.size();
int k = 0; /* 第i次迭代开始之前,k表示next[i-1]的值 */
next[1] = next[0] = 0;
for (int i = 2; i <= n; i++) {
for (; k != 0 && p[k] != p[i-1]; k = next[k]);
if (p[k] == p[i-1])
k++;
next[i] = k;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int strStr(string haystack, string needle) {// kmp algorithm
if (needle == "") return 0;
string s = haystack;
string p = needle;
int i=0,j=0;
int next[p.size()];
getNext(next,p); //init next
while ( i < s.size() && j < (int)p.size()) { //string.size() return unsigned int
if (s[i]==p[j]){
i++;
j++;
}else {
if (j==0) i++;
else j = next[j]; ///backtrack j
}
}
if(j==p.size()) return i - j;
else return -1;
}
// next
void getNext(int next[],string p){
next[0] = -1;
int k = -1,i = 0;
while (i < p.size()-1){
if(k == -1 || p[i] == p[k]){
next[++i] = ++k;
}
else k = next[k];
}
}
};