1.基本概念

串的定義：由零個或者多個字符組成的有限序列，又稱為字符串。
串的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)
串的抽象數(shù)據(jù)類型：

Data
串中元素僅由一個字符組成，相鄰元素具有前驅(qū)和后繼關(guān)系。

Operation
StrAssign(T,*chars):生成一個其值等于字符串常量chars的串T。
StrCopy(T,S):串S存在，由串S復(fù)制得串T。
ClearString(S):串S存在，將串清空。
StringEmpty(S):若串S為空，返回true，否則返回false。
StrLength(S):返回串S中的元素個數(shù)，即串的長度。
StrCompare(S,T):若S>T,返回值>0,若S=T,返回值=0，若S<T,返回值<0。
Concat(T,S1,S2):用T返回由S1與S2聯(lián)接而成的新串。
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位置之后，第一次出現(xiàn)串T的位置，如果沒有，則返回0。
Repalce(S,T,V):串S,T和V存在，T是非空串。用V替換主串S中出現(xiàn)的所有與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的字串

關(guān)于Index的兩種實現(xiàn)算法：樸素的模式匹配算法、KMP算法

2.樸素的模式匹配算法

/*主串S和子串T的長度,分別存儲在S[0]、T[0]中*/
int Index(string S, string T, int pos)
{
    int i = pos;//主串當(dāng)前位置的下標(biāo)，從pos的位置處開始匹配
    int j = 1;//子串當(dāng)前位置的下標(biāo)
    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;
    }
}

最壞情況下的時間復(fù)雜度為O((n-m+1)*m)

3.KMP算法

在樸素的模式匹配算法中，主串的i值是不斷回溯的，而部分回溯是沒有必要的，KMP算法就是避免這種不必要的回溯?！袄靡呀?jīng)部分匹配這個有效信息，保持i指針不回溯，通過修改j指針，讓模式串盡量地移動到有效的位置”。處理的關(guān)鍵就在于T串中是否有重復(fù)的問題，將T串各個位置的i值變化定義為數(shù)組next[j]：

• 0,當(dāng) 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;//主串當(dāng)前位置的下標(biāo)，從pos的位置處開始匹配
    int j = 1;//子串當(dāng)前位置的下標(biāo)
    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;
    }
}

參考文獻(xiàn)：

《大話數(shù)據(jù)結(jié)構(gòu)》 -----程杰