🔥概念

• 串即字符串是0个或多个字符组成的有限序列，字符个数n即字符串长度，n=0的串为空串（∅）
• 子串：串中的任意个连续的字符组成的子序列
• 主串：包含子串的串
• 字符串在主串的位置：字符在串中的序号，从1开始

🔥基本操作

大部分操作都和线性表操作类似，接下来不会进行过多的记录，只会重点记录其中几个

• StrAssign(&T,chars)：赋值操作。把串T赋值为chars。
• StrCopy(&T,S)：复制操作。由串s复制得到串T。
• StrEmpty(S)：判空操作。若s为空串，则返回TRUE，否则返回FALSE
• StrLength(S)：求串长。返回串S的元素个数。
• ClearString(&S)：清空操作。将S清为空串。
• DestroyString(&S)：销毁串。将串S销毁（回收存储空间）。
• Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串
• SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。
• Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
• StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S < T，则返回值<0。

🔥顺序存储

• 静态数组（定长顺序存储）

#define MAXLEN 255    //预定义最大串长
typedef struct{
  char ch[MAXLEN];
  int length;       //实际长度
}SString;

• 动态数组（堆分配存储）

typedef struct{
  char *ch;       //ch指向串的基地址
  int length;
}HString;
HString S;
S.ch = (char*)malloc(MAXLEN * sizeof(char));
S.length = 0;

• 常见字符串顺序存储方案

1. 在空间末尾放置length变量
2. 在空间开头放置length变量，这占用了0位置，使得数组下标和字符在串中的位序一致，缺点是字符串长度不能超过255否则length只有一位无法表示
3. 没有length变量，而是在字符串末尾放置一个 \0 表示结尾
4. 结合1、2的方案，舍弃第0位的使用，在末尾放置length变量，这会降低空间利用率

🔥链式存储

• 每个结点一个字符

typedef struct StringNode{
  char ch;
  struct StringNode * next;
}StringNode, * String;

• 每个结点多个字符，存储密度提高

typedef struct StringNode{
  char ch[4];
  struct StringNode * next;
}StringNode, * String;

🔥求子串

bool SubString(SString &Sub, SString S, int pos, int len){
  //越界
  if(pos+len-1>S.length)
    return false;
  for(int i=pos; i<pos+len; i++)      //将子串每一位依次赋值给Sub
    Sub.ch[i-pos+1]=S.ch[i];
    return true;
}

🔥比较操作

//比较，若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0
int StrCompare(SString S, SString T){
  for(int i=1;i<=S.length && i<=T.length; i++){
    if(S.ch[i]!=T.ch[i])
      return S.ch[i]-T.ch[i];
  }
  return S.length-T.length;   //若所有之前的字符都相同，则长度长的串更大，相同则为0
}

🔥模式匹配（查找）

使用比较操作

• 利用比较操作可以很容易实现查找模式串（即需要查找的子串）

int Index(SString S, SString T){
  int i=1; n=StrLength(S), m=StrLength(T);
  SString sub;      //暂存子串
  while(i<=n-m+1){
    SubString(sub,S,i,m);
    if(StrCompare(sub,T)!=0)  i++;    //不相同就继续位移比较
    else return i;      //返回子串在主串的位置
  }
  return 0;     //S中不存在T
}

朴素匹配模式算法

• 基于简单的数组操作，每次比较当比较到一个不相同就立刻进行位移

int Index(SString S,SString T){
  int k=1;
  int i=k, j=1;
  while(i<=S.length &&j<=T.length){
    if(S.ch[i]==T.ch[j]){
      ++i;
      ++j;        //继续比较后继字符
    }
    else{
      k++;      //检查下一个子串
      i=k;
      j=1;
    }
    if(j>T.length)
      return k;
    else
      return 0;
  }
}

• 这种算法缺点是，当一些子串经常与模式串部分的匹配时，使得扫描指针需要经常回溯，增加时间开销
• 模式匹配最坏时间复杂度是n*m，即主串与模式串长度之积

KMP算法

• 对朴素匹配模式算法进行优化，希望扫描指针能够像人眼查看字符串一样不用时常回看，只需要回溯模式串的指针

• next数组用来存放模式串指针回溯的位置
  

• 根据复杂的归纳，我们可以得到如下的求取next数组的方法
  

• 可以发现，next数组的前两个值一定分别是0和1

• next数组也能总结成以下式子
  

• 代码实现
  

• KMP算法只有出现子串和模式串时常匹配的情况时才会比朴素算法高效很多，其他情况不具有太多优势，朴素算法使用依然很广泛

KMP算法优化

• 如果next数组对应的字符是相同的，那么可以将它们的next值都设置为靠前的那个next值（尽可能小），这样可以尽可能减少回溯的距离，以此得到新的数组nextval进一步提升效率
  
• 代码实现