串

1.基本概念

串的定义：由零个或者多个字符组成的有限序列，又称为字符串。
串的存储结构：顺序存储结构、链式存储结构
串的抽象数据类型：

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串种pos位置之后，第一次出现串T的位置，如果没有，则返回0。
Repalce(S,T,V):串S,T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的字串。
StrInsert(S,pos,T)//1<=pos<=Strlength(S)+1在主串中pos位置之前插入字串T
StrDelete(S,pos,len)// 1<=pos<=Strlength(S),0<len<=Strlength(S)-pos+1  删除主串中pos位置起长度为len的字串

关于Index的两种实现算法：朴素的模式匹配算法、KMP算法

2.朴素的模式匹配算法

/*主串S和子串T的长度,分别存储在S[0]、T[0]中*/
int Index(string S, string T, int pos)
{
    int i = pos;//主串当前位置的下标，从pos的位置处开始匹配
    int j = 1;//子串当前位置的下标
    while ((i <= S[0]) && (j <= T[0]))
    {
        if (S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2;//主串回到上次匹配首位的下一位
            j = 1;//子串回到首处
        }
    }

    if (j > T[0])
    {
        return j - T[0];
    }
    else
    {
        return 0;
    }
}

最坏情况下的时间复杂度为O((n-m+1)*m)

3.KMP算法

在朴素的模式匹配算法中，主串的i值是不断回溯的，而部分回溯是没有必要的，KMP算法就是避免这种不必要的回溯。“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置”。处理的关键就在于T串中是否有重复的问题，将T串各个位置的i值变化定义为数组next[j]：

• 0,当 j = 1
• Max(k|1<k<j），P[0 ~ k-1] == P[j-k+1 ~ j-1]
• 1，其它情况

void get_next(string T, int *next)
{
    int i = 1;
    int j = 0;
    next[1] = 0;
    while (i < T[0])//T[0]表示为T串的长度
    {
        if (j == 0 || T[i] == T[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];//若字符不相同，则j值回溯
    }
}

int Index_KMP(string S, string T, int pos)
{
    int i = pos;//主串当前位置的下标，从pos的位置处开始匹配
    int j = 1;//子串当前位置的下标
    int next[255];
    get_next(T,next);
    while ((i <= S[0]) && (j <= T[0]))
    {
        if (j == 0 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];//j回退到合适的位置，i值不变
        }
    }

    if (j > T[0])
    {
        return j - T[0];
    }
    else
    {
        return 0;
    }
}

参考文献：

《大话数据结构》 -----程杰