【数据结构】第四章 串 (含KMP算法)

前端之家收集整理的这篇文章主要介绍了【数据结构】第四章 串 (含KMP算法)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

§4.1 串类型的定义

串中的任意个连续的字符组成的子序列称为该串的子串,包含子串的串相应地称为主串,通常称字符在序列中的序号为该字符的位置。

串的最小操作子集:串赋值 串比较 求串长 串连接 求子串


§4.2 串的表示和实现

串有3种机内的表示方法

4.2.1 定长顺序储存表示

4.2.2 堆分配储存表示:仍以一组地址连续的储存单元存放串值字符序列,但它们的存储空间实在程序执行过程中动态分配而得。在C语言中,存在一个称之为“”的自由存储区,并由C语言的动态分配函数Malloc和Free来进行管理。

4.2.3 串的块链储存表示:用链表储存串时,每个结点可以存放一个字符,也可以存放多个字符。 储存密度=串值所占的存储位/实际分配的储存位


§4.3 串的模式匹配算法(KMP算法)

4.3.1 求子串位置的定位函数 Index(S,T,pos)

子串的定位操作通常称作串的模式匹配(其中T称为模式串),是各种串处理系统中最重要的操作之一。

较简单的O(n^2)算法:从主串的第pos个字符起和模式的第一个字符比较之,以此类推,直至模式T中的每个字符依次和主串S中的一个连续的字符序列相当,则匹配成功。

4.3.2 模式匹配的一种改进算法(KMP算法)

※要点① 在KMP算法中主串是不存在回溯的,即每次如果出现失配即把模式串向右“滑动尽可能远的一段距离”。

※要点② next[j]=k表示当模式串中第j个字符与主串中相应字符失配时,在模式串中需重新和主串中该字符进行比较的位置。

由此可引出next[j]的定义:

-1 当j=1时

next[j] = Max{k| 1<k<j 且'p1..pk'='p(j-k+1)..pj'} 当此集合不空时(即最大的前缀 后缀相等的个数)

0 其他情况

如模式串'abaabcac'的next数组情况如下:

模式串 a ba a b c ac

next[j] -1 0 0 1 1 2 0 1

※要点③ (s是主串 p是模式串)若在匹配过程中s[i]=p[j],则i和j分别增1,否则,i不变,而j退到next[j]的位置再比较,若相等,则指针各自增1,否则j再退到下一个next值得位置,依次类推,直至下列两种可能:一种是j退到某个next值时字符比较相等,则指针各自增1,继续进行匹配;另一种是j退到值为-1(即模式串的第一个字符"失配"),则此时需将模式串继续向右滑动一个位置,即从主串的下一个字符s[i+1]起和模式串重新开始匹配。

上述过程伪代码可写成:

int KmpSearch(char* s,char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}  


※要点④ next数组的初级求法(证明略)

void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    int k = -1;//k记录的是next[j]
    next[0] = k;
    int j = 0;  
    while (j < pLen - 1) {
        /** next[j]=-1时,next[j+1]肯定是0;p[j]=p[k]时,next[j+1]=next[j]+1 */
        if (k == -1 || p[j] == p[k]) {
            ++k;
            ++j;
            next[j] = k;
        }
        else k = next[k]; 
    }
}  


※要点④next数组的优化求法(证明略)

void GetNext(char* p,int next[])
{
    int pLen = strlen(p);
    int k = -1;//k记录的是next[j]
    next[0] = k;
    int j = 0;
    while (j < pLen - 1) {
        /** next[j]=-1时,next[j+1]=next[j]+1 */
        if (k == -1 || p[j] == p[k]) {
            ++k;
            ++j;
            if(p[j] != p[k]) next[j] = k;
            else next[j] = next[k];
        }
        else k = next[k];
    }
}

推荐文章http://blog.csdn.net/v_july_v/article/details/7041827


§4.4 串操作应用举例

4.4.1 文本编辑

4.4.2 建立词索引表

猜你在找的数据结构相关文章