串

串即字符串，是由零个或多个字符组成的有限序列。S=’a1a2a3a4····an’
子串：串中任意连续的字符组成的子序列；
主串：包含子串的串；
子串在主串中的位置是子串第一个字符在主串中的位置；
串的数据对象限定为字符集（中文字符、英文字符、数字字符、标点字符等）

1.基本操作

(1)赋值操作:StrAssin(&T,chars)，把串T的值赋为chars;
(2)复制操作:StrCopy(&T,S),由串S复制得到T;
(3)判空操作:StrEmpty(S).若S为空串，返回True，否则返回False;
(4)求串长:StrLength(S).返回S的元素个数；
(5)清空操作:ClearString(&S).将S清为空串；
(6)销毁操作:DestroyString(&S).销毁串S;
(7)串联接:Concat(&T,S,M).用T返回S和M的连接而成的新串
(8)求子串:SubString(&Sub,S,pos,len).用Sub返回串S的第pos个字符起长度为len的子串；
(9)定位操作:Index(S,T).查找子串在主串的位置；
(10)比较大小:StrCompares(S,T);

2.顺序存储

  1. #define MaxLen 255
  2. typedef struct{
  3.     char ch[MaxLen];
  4.     int length;
  5. }SString;//定长顺序存储
  6. typedef struct{
  7.     char *ch;
  8.     int length;
  9. }HString;//堆分配存储
  10. HString S;
  11. S.ch=(char *)malloc(sizeof(char));
  12. S.length=0;//堆

3.链式存储

  1. typedef struct StringNode{
  2.     char ch[4];
  3.     struct StringNode * next;
  4. }StringNode,*String;//单独存储密度低

4.基本操作实现

4.1 求子串

  1. bool SubString(SString &Sub,SString S,int pos,int len){
  2.     if (pos+len-1>S.length)return false;
  3.     for (int i=pos;i<pos+len;i++){
  4.         Sub.ch[i-pos+1]=S.ch[i];
  5.     }
  6.     Sub.length=len;
  7.     return true;
  8. }

4.2 比较字符串的大小

  1. bool StrCompare(S,T){
  2.     for (int i=1;i<=S.length && i<=T.length;i++){
  3.         if (S.ch[i]!=T.ch[i])return S.ch[i]-T.ch[i];
  4.     }
  5.     return S.length-T.length;
  6. }

4.3 定位操作

  1. int Index(SStringS,SString t){
  2.     int i=1,n=SStringLength(S),m=SString(T);
  3.     SString Sub;
  4.     while (i<n-m+1){
  5.         SubString(Sub,S,i,m);//取子串
  6.         if (StrCompare(Sub,T)!=0)++i;
  7.         else return i;
  8.     }
  9.     return 0;
  10. }

4.4串的朴素模式匹配算法

  1. int Index(SStringS,SString t){
  2.     int k=1;
  3.     int i=k,j=1;
  4.     while (i<=S.length && j<=T.length){
  5.         if (S.ch[i]==T.ch[j]){++i;j++;}
  6.         else{k++;i=k;j=1;}
  7.     }
  8.     if (j<T.length)return k;
  9.     else return 0;
  10. }//最好时间复杂度O(m)，最坏O(nm);n为主串长度,m为模式串长度。

4.5KMP算法

  1. int Index_KMP(SString S,SString T,int next[]){
  2.     int i=1,j=1;
  3.     while (i<=S.length && j<=T.length)
  4.     {
  5.         /* code */
  6.         if (j==0||S.ch[i]==T.ch[j]){
  7.             ++i;
  8.             ++j;
  9.             }
  10.         else
  11.         {
  12.             j=next[j];
  13.         }
  14.         if (j>T.length)
  15.             return i-T.length;
  16.         else
  17.             return 0; 
  19.     }
  21. }

优化，next[]数组
求法：当第J个字符匹配失败时，由前1~j-1个字符组成的串记为S,则next[j]=S的最长相等前后缀长度+1；特别的next[1]=0

5.题型

求子串：包括本身和空串共有

4-串 - 图1%7D2%20%2B1%0A#card=math&code=%5Cfrac%7Bn%28n%2B1%29%7D2%20%2B1%0A)