@yanglt7 2018-10-21T15:50:18.000000Z 字数 4469 阅读 873

07_字符串匹配 -- BF算法、KMP算法

数据结构和算法

07_字符串匹配 -- BF算法、KMP算法

7.1字符串

7.1.1 定义

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。
一般记为 s = "a1a2a3......an" （n>0）
串可以是空串，即没有字符，直接由""表示（注意里面没有空格，只是双引号），或者可以用希腊字母 Φ 来表示。
子串与主串，例如"HopeStudio" 是 "HopeStudio.com"的子串，反之则倒过来。

7.1.2 字符串的比较

比较字符串里每个字符的ASCII码大小。
其实比较大小没有多大意义，字符串的比较我们更重视是否相等。

7.1.3 字符串的存储结构

字符串的存储结构与线性表相同，也分为顺序存储结构和链式存储结构。
字符串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。
按照预定义的大小，为每个定义的字符串分配一个固定长度的存储区，一般用定长数组来定义。
与线性表相似，既然是固定长度的存储区，就存在一个空间分配不灵活的问题，那么会考虑用链式存储结构。
不同的是，字符串我们一般都是连在一起表述的，“断章取义”的情况并不多，所以习惯上我们通常还是会直接定义一个足够长度的存储区来存储的。

7.2 BF (Brute Force) 算法

BF算法属于朴素的模式匹配算法，它的核心思想是：
- 有两个字符串S和T，长度为N和M。首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向右移动一个字符的位置，再依次进行比较。
- 该算法最坏的情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)
在这里S是主串，T是字串，这种子串的定位操作通常称作串的模式匹配。
代码实现

#include <stdio.h>
typedef char *String;
//返回子串T在主串S的第pos个字符后(含第pos个位置)第一次出现的位置
//若不存在，则返回-1
//采用BF算法，这里的位置全部以从1开始计算为准，其中T非空，1<=pos<=T[0]
int Index_BF( String S, String T , int pos )
{
    int i = pos;  //主串当前正待比较的位置，初始为pos
    int j = 1;   //子串当前正待比较的位置，初始为1
    while( i <= S[0] && j <= T[0] )
    {
        if( S[i] == T[j] )   //如果当前字符相同，则继续向下比较
        {   
            i++;
            j++;
        }
        else   //如果当前字符不同，则i和j回退，重新进行匹配
        {   
            i = i-j+2;
            j = 1;
        }
    }
    if( j > T[0] )
    {
        return i - T[0];
    }       
    else
    {
        return -1;
    }
}
int main()
{
    char S[255];
    char T[255];
    char c, e;
    int n = 1;
    int k = 0;
    int pos;
    printf("请输入主串： ，并以#作为结束标志！\n"); 
    scanf("%c", &c);
    while( c != '#' )
    {
        S[n++] = c;
        S[n] = '\0';
        scanf("%c", &c);
    }
    S[0] = n-1; 
    printf("请输入子串： ，并以#作为结束标志！\n");
    scanf("%c", &e);
    while( e != '#' )
    {
        T[k++] = e;
        T[k] = '\0';
        scanf("%c", &e);
    }
    T[0] = k-1; 
    printf("请输入主串中开始进行匹配的位置（首字符位置为1）：\n");
    scanf("%d", &pos);
    int result = Index_BF( S, T, pos );
    if( result != -1 )
    {
        printf("主串与子串在主串的第%d个字符（首字符的位置为1）处首次匹配", result);
    }           
    else
    {
        printf("无匹配子串\n");  
    }
    return 0;
}

7.3 KMP算法

KMP算法是( D.E.Kunth, J.H.Morris 和 V.R.Pratt )的研究结果，大大的避免重复遍历的情况，全称叫做克努特-莫里斯-普拉特算法，简称KMP算法。

7.3.1 回溯

回溯就是坚持条条大路通罗马的决心，遇到挫折就回到跌倒的地方重新爬起来，继续往前，思想是好的，但效率低下。
KMP算法的核心就是避免不必要的回溯，那么什么是不必要的呢，问题由模式串决定，不是由目标决定。

7.3.2 思路启发

思路启发一

S	14	I	l	o	v	e	F	i	s	h	C	.	c	o	m
i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
T	5	I	l	o	v	x
j	0	1	2	3	4	5

- 思路启发二

S	13	w	w	w	.	F	i	s	h	C	.	c	o	m
i	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	3	w	w	.
j	0	1	2	3

- 思路启发三

S	12	b	b	s	b	b	s	.	F	i	s	h	C
i	0	1	2	3	4	5	6	7	8	9	10	11	12
T	6	b	b	s	b	b	c
j	0	1	2	3	4	5	6

- 思路启发四

S	8	s	s	s	s	s	s	s	x
i	0	1	2	3	4	5	6	7	8
T	5	s	s	s	s	b
j	0	1	2	3	4	5

7.3.3 k数组

给模式匹配串添加一个k数组（也就是KMP算法中非著名的next数组）。
这是一个“智能”的数组，因为他指导着模式匹配串下一步该用第几号元素去进行匹配。
思路启发一

S	14	I	l	o	v	e	F	i	s	h	C	.	c	o	m
i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
T	5	I	l	o	v	x
j	0	1	2	3	4	5
k		0	1	1	1	1

思路启发二

S	13	w	w	w	.	F	i	s	h	C	.	c	o	m
i	0	1	2	3	4	5	6	7	8	9	10	11	12	13
T	3	w	w	.
j	0	1	2	3
k		0	1	2

思路启发三

S	12	b	b	s	b	b	s	.	F	i	s	h	C
i	0	1	2	3	4	5	6	7	8	9	10	11	12
T	6	b	b	s	b	b	c
j	0	1	2	3	4	5	6
k		0	1	2	1	2	3

思路启发四

S	8	s	s	s	s	s	s	s	x
i	0	1	2	3	4	5	6	7	8
T	5	s	s	s	s	b
j	0	1	2	3	4	5
k		0	1	2	3	4

7.4 KMP算法之next数组代码原理分析

T	9	a	b	a	b	a	a	a	b	a
下标	0	1	2	3	4	5	6	7	8	9
next		0	1	1	2	3	4	2	2	3

i （后缀） = 1 2 。3 4 5 6 7 。8 9
j （前缀） = 0 1 0 1 2 3 4 2 1 2 3

next数组：当模式匹配串T失配的时候，next数组对应的元素指导应该用T串的哪个元素进行下一轮的匹配。

void get_next( String T, int *next )
{
    j = 0;
    i = 1;
    next[1] = 0;
    while( i < T[0] )
    {
        if( 0 == j || T[i] == T[j] )
        {
            i++；
            j++;
            next[i] = j;
        }
        else
        {
            //j回溯
            j = next[j];
        }
    }
//因为前缀是固定的，后缀是相对的
}

7.5 KMP算法之实现及优化

7.5.1 获取next数组的代码实现

测试版

#include <stdio.h>
typedef char * String;
void get_next( String T, int *next )
{
    int j = 0;
    int i = 1;
    next[1] = 0;
    while( i < T[0] )
    {
        if( 0 == j || T[i] == T[j] )
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            //j回溯
            j = next[j];
        }
    }
//因为前缀是固定的，后缀是相对的
}
int main()
{
    char str[255] = " ababaaaba";
    int next[255];
    int i = 1;
    str[0] = 9;
    get_next( str, next );
    for( i=1; i < 10; i++ )
    {
        printf("%d ", next[i]);
    }
    return 0;
}

改正版

#include <stdio.h>
typedef char * String;
void get_next( String T, int *next )
{
    int j = 0;
    int i = 1;
    next[1] = 0;
    while( i < T[0] )
    {
        if( 0 == j || T[i] == T[j] )
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            //j回溯
            j = next[j];
        }
    }
//因为前缀是固定的，后缀是相对的
}
int main()
{
    char T[255];
    int next[255];
    int i = 1;
    int n = 1;
    char c;
    printf("请输入需要获取next数组的字符串：，并以#作为结束标志!\n");
    scanf("%c", &c);
    while( c != '#' )
    {
        T[n++] = c;
        T[n] = '\0';
        scanf("%c", &c);
    }
    T[0] = n;
    get_next( T, next );
    for( i=1; i < T[0]; i++ )
    {
        printf("%d ", next[i]);
    }
    return 0;
}

7.5.2 KMP算法匹配主串和子串

#include <stdio.h>
typedef char * String;
void get_next( String T, int *next )
{
    int j = 0;
    int i = 1;
    next[1] = 0;
    while( i < T[0] )
    {
        if( 0 == j || T[i] == T[j] )
        {
            i++;
            j++;
            if( T[i] != T[j] )
            {
                next[i] = j;
            }
            else 
            {
                next[i] = next[j];
            }
        }
        else
        {
            //j回溯
            j = next[j];
        }
    }
//因为前缀是固定的，后缀是相对的
}
//返回子串T在主串S第pos个字符的位置
//若不存在，则返回-1
int Index_KMP( String S, String T, int pos )
{
    int i = pos;
    int j = 1;
    int next[255];
    get_next( T, next );
    while( i <= S[0] && j <= T[0] )
    {
        if( 0 == j || S[i] == T[j] )
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if( j > T[0] )
    {
        return i - T[0];
        printf("%d ", i - T[0]);
    }
    else
    {
        return -1;
    } 
}
int main()
{
    char S[255] ;
    char T[255] ;
    int next[255];
    int n = 1;
    int k = 0;
    int pos;
    char c,e;
    printf("请输入主串： ，并以#作为结束标志！\n") ;
    scanf("%c", &c);
    while( c != '#' )
    {
        S[n++] = c;
        S[n] = '\0';
        scanf("%c", &c);
    }   
    S[0] = n-1;
    printf("S[0]=%d", S[0]);    
    printf("请输入子串： ，并以#作为结束标志！\n");
    scanf("%c", &e);
    while( e != '#' )
    {
        T[k++] = e;
        T[k] = '\0';
        scanf("%c", &e);
    }
    T[0] = k-1; 
    printf("T[0]=%d", T[0]);    
    printf("请输入主串中开始进行匹配的位置（首字符位置为1）：\n");
    scanf("%d", &pos);
    int result = Index_KMP( S, T, pos ); 
    if( result != -1 )
    {
        printf("主串与子串在主串的第%d个字符（首字符的位置为1）处首次匹配", result);
    }
    else
    {
        printf("无匹配子串\n");  
    }
    return 0;
}