一、串的定义及基本运算

串（或字符串） ：是由零个或多个字符组成的有序序列。
一般记为 $s='\displaystyle a_1\displaystyle a_2 ... \displaystyle a_n'$ （n≧0）

串名：s是串的名。
串值：用单引号括起来的字符序列。
长度：串中字符的数目n。
空串：零个字符的串。
子串：串中任意个连续的字符组成的子序列。
注：空串是任意串的子串，任意串是其自身的子串。
主串：包含子串的串相应的被称为主串。(在串中的位置则以子串的第一个字符的位置来表示)
空格串：由一个或多个空格组成的串 ‘ ’ 。
用 “Ф” 来表示空串。
通常称字符在序列中的序号为该字符在串中的位置。
当且仅当两个串的值相等时，称这两个串是相等的。

二、串的基本实现

1.串的定长顺序存储表示及相关函数

#define MaxStrLen 255 //最大串长
typedef struct{
    char ch[MaxStrLen];
    int length;
}SString;

void StrAssign(SString *T, char str[]);//串的生成
void StrCopy(SString *T, SString *S);//串的复制
bool StrEmpty(SString *T);//判定串是否为空
int StrCompare(SString *T, SString *S);//串比较
int StrLength(SString *T);//求串长
void ClearString(SString *T);//将T清空为空串
bool Concat(SString *Str, SString *T, SString *S);//串联接
bool SubString(SString *Str, SString *T, int pos, int len);//求子串
int Index(SString Str, SString T, int pos);//子串定位
void StrInsert(SString *T, int pos, SString *S);//字串的插入
void DispStr(SString *T);//输出串
int BFIndex(SString *S, SString *T); //子串定位，BF算法
int KMPIndex(SString *S, SString *T); //子串定位，KMP算法
void GetNext(SString *T, int next[]);

2.串赋值

void StrAssign(SString *T, char str[]){
    int i;
    for(i = 0; str[i]!='\0'; i++){
        T->ch[i] = str[i];
    }
    T->length = i;
}

3.串的复制

void StrCopy(SString *T, SString *S){
    for(int i = 0; i < T->length; i++){
        S->ch[i] = T->ch[i];
    }
    S->length = T->length;
}

4.判断串是否为空串

bool StrEmpty(SString *T){
    if(T->length == 0) return true;
    else return false;
}

5.串比较

int StrCompare(SString *T, SString *S){
    if(T->length > S->length)
        return 1;
    else if(T->length == S->length)
        return 0;
    else return -1;
}

6.求串长

int StrLength(SString *T){
    return T->length;
}

7.将串清空

void ClearString(SString *T){
    for(int i = 0; i < T->length; i++){
        T->ch[i] = '\0';
    }
    T->length=0;
}

8.串联结

bool Concat(SString *Str, SString *T, SString *S){
    int i, j;
    if(T->length + S->length <= MaxStrLen){
        for(i = 0; i < T->length; i++){
            Str->ch[i] = T->ch[i];
        }
        for(j = 0; i < T->length + S->length; i++, j++){
            Str->ch[i] = S->ch[j];
        }
        return true;
    }
    else if(T->length < MaxStrLen){
        for(i = 0; i < T->length; i++){
            Str->ch[i] = T->ch[i];
        }
        for(j = 0; i < MaxStrLen; i++, j++){
            Str->ch[i] = S->ch[j];
        }
        return false;
    }
    else{
        for(i = 0; i < MaxStrLen; i++){
            Str->ch[i] = T->ch[i];
        }
        return false;
    }
}

9.求子串

bool SubString(SString *Str, SString *T, int pos, int len){
    int i, k;
    Str->length = 0;
    if(pos < 1 || pos > T->length || len < 0 || len > T->length-pos+1){
        return false;
    }
    for(i = 0, k = pos-1; k < pos + len -1; k++, i++){
        Str->ch[i] = T->ch[k];
    }
    Str->length = i;
    return true;
}

10.子串的插入

void StrInsert(SString *T, int pos, SString *S){
    if(pos <= 0 || pos > T->length+1){
        printf("位置不合理！");
        return;
    }

    int i, j;
    SString temp;
    if(T->length + S->length <= MaxStrLen){
        for(i = pos-1, j= 0; i < T->length; i++, j++){
            temp.ch[j] = T->ch[i];
            temp.length++;
        }
        for(i = pos-1, j= 0; j < S->length; i++, j++){
            T->ch[i] = S->ch[j];
            T->length++;
        }
        for(j = 0; j < temp.length; i++, j++){
            T->ch[i] = temp.ch[j];
        }
    }
    else{
        printf("插入失败！");
        return;
    }
}

11.输出串

void DispStr(SString *T){
    if(T->length > 0){
        for(int i = 0; i < T->length; i++){
            printf("%c", T->ch[i]);
        }
    }
    else
        printf("字符串为空！");
}

12.子串定位——BF算法
下详述
13.子串定位——KMP算法
下详述

三、串的模式匹配算法

1.朴素的串匹配算法（基本的模式匹配算法）Brute-Force

代码如下（示例）：

int BFIndex(SString *S, SString *T){
    int i = 0, j = 0; 
    while(i < S->length && j < T->length){
        if(S->ch[i] == T->ch[j]){
            i++;
            j++;
        }
        else{
            j = 0;
            i = i - j + 1;
        }
    }
    if(j >= T->length) //匹配成功
        return i-T->length;
    else return -1; //匹配失败
}

2.改进的模式匹配算法（KMP算法）

1.获取next数组

在这里插入代码片void GetNext(SString *T, int next[]){
    int j = 0, k = -1;
    next[0] = -1;
    while(j < T->length - 1){
        if(k == -1 || T->ch[j] == T->ch[k]){
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}

2.KMP算法

int KMPIndex(SString *S, SString *T){
    int next[MaxStrLen], i = 0, j = 0;
    GetNext(T, next);
    while (i < S->length && j < T->length){
        if(j == -1 || S->ch[i] == T->ch[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if(j >= T->length)
        return i - T->length;
    else
        return -1;
}