一、串

1、定义

由零个或多个字符组成的有限序列，一般可以记为 ，其中

• 可以是字母、数字或其他字符
• 指的是该字符在串中的位置
• 指的是该字符串的长度
• 零个字符的串则被称之为空串

2、基本概念

1. 子串：串中任意个连续的字符组成的子系列
2. 主串：包含子串的串
3. 位置：字符在序列中的序号（从 1 可开始）
4. 空格串：只包含空格的串，注意与空串的区别（‘ ’与 ）

3、基本操作

• StrAssign (&T, chars)：赋值，把串 T 赋值为 chars
• StrCopy (&T, S)：复制，由串 S 复制得串T
• StrEmpty (S)：判空
• StrCompare (S, T)：比较两个字符串长度
  • 若 S>T，返回值>0
  • 若 S=T，返回值=0
  • 若 S<T，返回值<0
• StrLength (S)：求串长度
• ClearString (&S)：清空串
• Concat (&T, S1, S2)：拼接，用 T 返回 S1和 S2 平拼接而成的新串
• SubString (&Sub, S, pos, len)：求子串，用 Sub 返回串 S 的第 pos 个字符串起长度为 len 的子串
• Index (S, T，pos)：定位，若主串 S 中存在与串 T 相同的子串，则返回它在主串 S 中第一次出现的位置，否则返回 0
• Replace (&S, T, V)：用 V 替换主串 S 在中出现的所有与 T 相等的不重叠的子串
• StrInsert (&S, pos, T)：在串 S 的第 pos 个字符之前插入串 T
• StrDelete (&S, pos, len)：从串 S 在中删除第 pos 个字符起长度为 len 的子串
• DestoryString (&S)：销毁（释放空间）

4、存储结构

（1）顺序表示

用一组地址连续的存储单元来存储串中的字符序列，在字符串的末尾用 ‘\0’ 表示结束，它不算做字符串的长度，但是需要占用存储空间

（2）链式表示

与线性表不同，在串的存储过程中存在结点大小的问题，每个结点可以只存放一个字符，也可以存放多个字符。没占满的位置用 # 补齐

注： 存储密度小（如结点大小为 1 时），运算处理方便，但是存储用量过大；但是如果在串处理过程中需要进行内、外存交换的话，则会因为内外存操作过多而影响处理的总效率。

串值的链式存储结构对某些串操作有一定的方便之处（如联接操作等），但是总的来说，另外两种存储结构更加灵活。

5、串的模式匹配

子串的定位操作称为串的模式匹配

（1）朴素模式识别算法

朴素算法是一种纯暴力算法，他将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的子串/或者全部不匹配为止

int Index(String S,String T,int pos)
{
    //字符串从1位置开始存储
    int i=1;//i指针指向主串S
    int j=1;//j指针指向模式串T
    int k=i;//k用来记录下次主串回溯的位置
    while(i<=S.len && j<=T.len)
    {
        if(S[i]==T[j])
        {
            ++i;
            ++j;
        }
        else//不匹配
        {
            j=1;//模式串从第一个位置继续开始匹配
            i=++k;//主串从k+1位置开始比较
        }
    }
    if(j>T.len)//如果是模式串扫描完了，说明匹配到了，那么此时k记录的就是模式串起始位置
        return k;
    else
        return 0;
}

算法效率分析

• 最好情况：时间复杂度为
• 平均情况：平均查找次数为 ，时间复杂度为
• 最坏情况：

（2）KMP 算法

难点 KMP 算法是对朴素算法的优化，每当一趟匹配过程中出现字符比较不相等时，不需要回溯 i 指针，而是利用已经得到的“部分匹配”的结果，将模式向右“滑动”尽可能远的一段距离后，继续进行比较

• Next[j]的计算方法：

  1. 第一位为 0, 的第二位为 1
  2. 如果存在最长相等前后缀 n，则等于 n+1
  3. 如果不存在，则为 1

• Nextval[j]的计算方法：

  1. 第一位为 0
  2. 如果第二位的值等于第一位的值，则为 0；反之为 1
  3. 从第三位开始，由 next[j]指路，若当前值=next 在指向的值，则为别人的 nextval 值；反之则为当前的 next 值

计算 next 数组的函数 c void get_next(string T,int next[]) { int i=1,j=0; next[1]=0; while(i<T[0]) { if(j==0 || T[i]==T[j]) { i++; j++; next[i]=j; } else { j=next[j]; } } }