字符串匹配算法
给定一行字符串文本为主串，另一个字符串为模式串，在主串中查找模式串首次出现的位置，并返回其位置下标。
蛮力法（BF）
即依次比较主串和模式串的每一个字母，碰见不匹配的字母时，主串和模式串从头右移一位重新匹配，直至成功或遍历完成。
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
37
38
|
int BF(char S[],char T[]){
int i,k,m;
int j = strlen(T);
for( i = 0 ; i < strlen(S) - j ; i++ ){
k = i ;
m = 0 ;
while(k <= i + j){
if( S[k++] != T[m++] )
break;
if( k == i+j ){
return i + 1;
}
}
}
printf("error!");
return 0;
}
int BF(char T[],char S[]){
int index = 0;
int i = 0 , j = 0;
while(S[i] != '\0' && T[j] != '\0'){
if(S[i] == T[j]){
i++;
j++;
}else{
j = 0;
index++;
i = index;
}
}
if(T[j] == '\0')
return index+1;
else
return -1;
}
|
求字符串相等最大真前后缀
字符串的真前/后缀指不包括字符串自身的前缀/后缀。给定一个字符串，编写函数，求解字符串T所有前缀子串（包括自己）的最大相等真前后缀的长度，并存入next数组中。
蛮力法
从长度为1开始判断，长度为1时输出0；长度为n（n>=2），判断前n-1个字符和后n-1个字符是否相同，若不相同则减小比较的长度。知道找出相等真前后缀为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void MaxAffixLength(char T[],int next[],int length){
int i,j,len;
memset(next,0,length*sizeof(int));
for( i = 1 ; T[i] != '\0' ; i++ ){
for( len = i-1 ; len >= 1 ; len-- ){
for( j = 0 ; j < len ; j++ ){
if( T[j] != T[i-len+j+1] ) break;
}
if( j == len ){
next[i] = len;
break;
}
}
}
}
|
根据已求求下一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void PMT(char T[],int next[]){
int i ,j ;
memset(next,0,NUM*sizeof(int));
next[0] = 0;
if(T[0] == T[1]){
next[1] = 1;
}else{
next[1] = 0;
}
for( i = 2 ; T[i] != '\0' ; i++ ){
j = i;
while( j != 0 ){
if( T[i] == T[next[j-1]] ){
next[i] = next[j-1] + 1;
break;
}else{
j = next[j-1];
}
}
}
}
|
KMP算法
有效利用已匹配的前缀，减少指针回溯。
整体思路：在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮中直接把两者对齐，从而实现模式串的快速移动。
（图源知乎）
next数组是我们上面求的最大真前后缀数组进行处理后得到的。
处理：将每一位的最大真前后缀字符数向后移一格。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int kmp(char S[],char T[],int next[])
{
int j = 0;
for (int i = 0; i < strlen(S); i++)
{
while (j > 0 && S[i] != T[j])
{
j = next[j];
}
if (S[i] == T[j]) {
j++;
}if (j == strlen(T)) {
return i - strlen(T) + 1;
}
}
return -1;
}
|
