串的模式匹配：在主串中，找到与模式串相同的子串，并返回其所在位置。
其实就是给出一个串abc，找到abc在主串的位置【abc都要匹配】

模式串：给出一个串abc
子串：主串中的abc【可能没有】

1. 串的朴素模式匹配算法

1.1 方法一：用k记录位置

1.2 方法二：不用k

时间复杂度：设模式串长度为m，主串长度为n

• 匹配成功的最好时间复杂度： O(m)
• 匹配失败的最好时间复杂度： O(n)
• 最坏时间复杂度： O(nm)

---

2. KPM算法

朴素模式匹配算法的缺点：
当某些子串与模式串能部分匹配时，主串的扫描指针 i 经常回溯，导致时间开销增加。最坏时间复杂度 O(nm) 。

kmp可以使 i 不回溯，并且 j 会跳转到某个地方X【由next数组决定，j=1到地方X的内容比较时—>就已经相等】

2.1 求next数组

串的前缀：包含第一个字符，且符不包含最后一个字的子串。
串的前缀：包含最后一个字符，且不包含第一个字符的子串。
注：子串如果为a，则前缀、前缀均为空集

next 数组的计算方法：
当第 j 个字符匹配失败时，将前（1~j-1）个字符组成的串记为S，
则：next[j] = S的最长相等前后缀长度+1。
特别地，next[1]=0。

例1：求模式串“abcabd”的 next 数组。

例2：求模式串：’ababaa’ 的 next 数组。

---

2.2 KPM 算法代码实现

// 获取模式串T的next[]数组  ----这个函数好像不考，会求next数组即可
void getNext(SString T, int next[]){ 
    int i=1, j=0;  
    next[1]=0;  
    while(i<T.length){   
        if(j==0 || T.ch[1]==T.ch[j]){ 
            ++i; ++j;      
            next[i]=j;  
        }else      
            j=next[j]; 
    }
}

// KPM算法，求主串S中模式串T的位序，没有则返回0
int Index_KPM(SString S, SString T){   
    int i=1, j=1;  
    int next[T.length+1]; 
    getNext(T, next);  
    while(i<=S.length && j<=T.length){  
        if(j==0 || S.ch[i]==T.ch[j]){   
            ++i; ++j;   
        }else   
            j=next[j];   
    }    
    if(j>T.length)   
        return i-T.length;  
    else
        return 0;
}

int main() {
	SString S={"ababcabcd", 9};
	SString T={"bcd", 3};
	printf("%d ", Index_KPM(S, T));	//输出9
}

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
34
35
36

KPM 算法：当子串和模式串不匹配时，主串指针 i 不回溯，模式串指针 j=next[j]。KMP 算法的平均时间复杂度为： O(n+m)。

---

2.3 next数组进一步优化：nextval数组

求nextval数组步骤：
先求next数组。再从左到右，找是否相等，相等则替换

//不考具体算法吧？会求nextval数组即可
void getNextval(SString T, int nextval[]){
    int i=1,j=0;
    nextval[1]=0;
    while(i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            ++i; ++j;
            
            if(T.ch[i]!=T.ch[j])
                nextval[i]=j;//和next一样
            else
                nextval[i]=nextval[j];
        }else
            j=nextval[j];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

例子2