第5章 串

串(string)是由零个或多个字符组成的有限序列,又名叫字符串。

5.2 串的定义

串(string)是由零个或多个字符串组成的有限序列,又名叫字符串。

一般记为 s=“a1a2......an”(n>=0),其中n是串的长度,n为零的串称为空串。

5.3 串的比较

给定两个串:s=“a1a2....an”,t="b1b2....bn",当满足以下条件之一时,s<t

  1. n<m, 且a=b(i=1, 2, ......, n)。

    例如s="hap", t="happy",s<t。

  2. 存在某个k<=min(m, n),使得a = b(i=1, 2, ......, k-1),a<b。

    例如s="happen",t="happy",前4个字母相同,第5个'e' < 'y',则s<t。

5.4 串的抽象数据类型

ADT 串(string)
Data
    串中元素仅由一个字符组成,相邻元素具有前驱和后继的关系。
Operation
    StrAssign(T, *chars):生成一个其值等于字符串常量chars的串T。
    StrCopy(T,S):串S存在,由串S复制得串T。
    ClearString(S):串S存在,将串清空。
    StringEmpty(S):若串S为空,返回true,否则返回false。
    StrLength(S):返回串S的元素个数,即串的长度。
    StrCompare(S,T):若S>T,返回值>0,若S=T,返回0,若S<T,返回值<0。
    Concat(T, S1, S2):用T返回由串S1,S2拼成的新串。
    SubString(Sub,S,pos,len):串s存在, 1<=pos<=StrLength(S),且0<=len<=StrLength(S)-pos+1,
                             用Sub返回串S的第pos个字符其长度为len的子串。
    Index(S,T,pos):串S和T存在,T是非空字符串,1<=pos<=StrLength(S)。若主串S中存在和串T值相同的子                               串,则返回它在主串s中的第pos个字符串之后第一次出现的位置,否则返回0。
    Replace(S,T,V):串S,T和V存在,T是非空串。用V替换主串S中出现的所有与T相等的不重叠子串。
    StrInsert(S,pos,T):串S和T存在,1<=pos<=StrLength(S)+1。在串S的第pos个字符之前插入串T。
    StrDelete(S,pos,len):串S存在,1<=pos<=StrLength(S)-len+1。从串S中删除第pos个字符起长度为len                         的子串。
endADT

Index的实现算法。

/*
* T为非空串。若主串S中第pos个字符之后存在与T相等的子串,
* 则返回第一个这样的子串在S中的位置,否则返回0。
*/
int Index(String S, String T, int pos)
{
    int n, m, i;
    String sub;
    if(pos > 0)
    {
        n = StrLength(S);
        m = StrLength(T);
        i = pos;
        while(i < n - m + 1)
        {
            SubString(S, T, i , m);     //取主串第i个位置,长度与T相等子串给sub
            if(StrCompare(sub,T) != 0)  //如果两串不相等
                ++i;
            else
                return i;
        }
    }
    return 0;                           //若无子串与T相等,返回0。
}

5.5 串的存储结构

5.5.1 串的顺序存储 结构

当两个串的连接Concat、新串的插入StrInsert、以及字符串的替换Replace都有可能使得串序列的长度超过数组的最大长度MaxSize,需要重新分配。

5.5.2 串的链式存储结构

5.6 朴素的模式匹配算法

查找一个单次在一篇文章中的定位问题,这种子串的定位操作通常称为串的模式匹配。

对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做T的长度的小循环,直到匹配成功或全部遍历完成为止。

不考虑使用串的其他操作来实现模式匹配算法Index。现在考虑不用串的其他操作,而是只用基本的数组来实现同样的算法。注意我们假设主串S和要匹配的子串T的长度存在S[0]和T[0]中。实现代码如下:

/*
* 返回子串T在主串S中第pos个字符之后的位置,若不存在,则函数返回值为0
* T非空,1<=pos<=StrLength(S)。
*/
 int Index(String S, String T, int pos)
 {
     int i = pos;
     int j = 1;
     while (i <= S[0] && j <= T[0])
     {
         if (S[i] == T[j])
         {
             i++;
             j++;
         }
         else   //指针回退,重新匹配
         {
             i = i - j + 2;     //i退回到上次匹配首位的下一位
             j = 1;
         }
     }
     if (j > T[0])
         return i - T[0];
     else
         return 0;
 }

5.7 KMP模式匹配算法

KMP(D.E.Knuth、J.H.Morris、V.R.Pratt)算法,一个模式匹配算法,可以大大避免重复遍历的情况。

5.7.1 KMP模式匹配算法原理

5.7.2 next数组值推导

5.7.3 KMP模式匹配算法实现

//通过计算返回子串T的next数组
void get_next(String T, int *next)
{
    int i,j;
    i = 1;
    j = 0;
    next[1] = 0;
    while ( i < T[0])                   //此处T[0]表示串T的长度
    {
        if(0 == j || T[i] == T[j])      //T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];                //若字符不相同,则j回溯
    }
}

这段代码的目的就是为了计算出当前要匹配的串T的next数组。

/*
* 返回子串T在主串S中第pos个字符之后的位置,若不存在,则函数返回值为0
* T非空,1<=pos<=StrLength(S)。
*/
int Index_KMP(String S, String T, int pos)
{
    //i用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配
    int i = pos;
    //j用于子串T中当前位置下标值
    int j = 1;
    int next[255];
    get_next(T, next);      //对串T作分析,得到next数组
    while ( i <= S[0] && j <= T[0])     //若i小于S的长度且j小于T的长度时,循环继续
    {
        if (0 == j || S[j] == T[j])     //两字母相等则继续,相对于朴素算法增加了j=0判断
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];                //j退回到合适的位置,i值不变
        }
    }
    if (j > T[0])
        return i-T[0];
    else
        return 0;
}

5.7.4 KMP模式匹配算法改进

/*
* 求模式串中T的next函数修正值并存入数组nextval
*/
void get_nextval(String T, int *nextval)
{
    int i, j;
    i = 1;
    j = 0;
    nextval[1] = 0;
    while (i < T[0])
    {
        if (j == 0 || T[i] == T[j])
        {
            ++i;
            ++j;
            if (T[i] != T[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}
01-07 06:19