【数据结构】【串】

串，即字符串 是有零个或多个字符组成的有限序列 

字符在主串中的位置：字符在串中的序号(位序从1开始；空格也是字符)

串的基本操作主要以子串作为操作对象

设计串的时候 ch[0]废弃不用，并且在末尾添加变量length记录串的长度。

ch[0]废弃不用：字符的位序和数组下标相同。但char之战1B也就是8bit，以功能存储0~255个数，空间有限。

串的存储

//串的顺序存储
#define MAXLEN 255
typedef struct{  //静态
  char ch[MAXLEN];
  int length;
}SString;

typedef struct{  //动态
  char *ch;
  int length;
}HString;
HString S;
S.ch = (char *)malloc(MAXLEN * sizeof(char));
S.length=0;

//串的链式存储
typedef struct StringNode{  
  //char ch;//1B 存储密度低
  char ch[4];
  struct StringNode * next;//4B
}StringNode,* String;

串的基本操作

//求子串
bool SubString(SString &Sub,SString S,int pos,int len){ //第pos个字符起是长度为len的子串,Sub返回想要找到的子串的内容
   if(pos+len-1 > S.length)//判断子串是否越界
       return false;
   for(int i=pos;i<pos+len;i++)//将Sub的值复制到ch数组里，并且把长度设为len
       Sub.ch[i-pos+1] = S.ch[i];
   Sub.length = len;
   return true;
}

//比较串大小 若S>T 返回值>0,=<同理
bool 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
}

//定位操作 若主串S中存在与子串T值相同的子串，则傅安辉它在主串中第一次出现的位置
int Index(SString S,SString T){
  int i=1,n=StrLength(S),m=StrLength(T);//n表示S的长度
  SString sub;
  while(i<=n-m+1){
    SubString(sub,i,m);
    if(StrCompare(sub,T)!=0) ++i;
    else return i;
  }
  return 0;
}

 串的朴素模式匹配

子串：主串中存在的

模式串：想尝试在主串中寻找的串，未必存在

串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置

// 串的朴素模式匹配
int Index(SString S,SString T){
int k=1;//指向当前主串中被遍历的字符，因为0号位弃之不用故从1开始
int i=k,j=1;//i k 共同指向S j指向T
while(i<S.length && j<T.length)//若不匹配i就回溯
{
    if(S.ch[i]==T.ch[i]){
    ++i;
    ++j
    }else{
    k++;
    k=i;
    j=1;//若不相等j还指向模式串第一个位置
    }
}
if(j>T.length)
    return k;
else
    return 0;
}

若模式创长度 为m,主串长度为n，则匹配成功的最好时间复杂度：O（m）;匹配失败的最好时间复杂度：O（n）;最坏的时间复杂度：O（nm）

KMP算法——朴素模式优化

//KMP算法
int Index_KMP(SString S,SString T,int next[]){
   int i=1,j=i;
   while(i<=S.length && j<T.length){
     if(j==0||S.ch[i]==T.ch[j]){
           ++i;
           ++j;
   }
     else
       j=next[j];
}
if(j>T.length)
    return i-T.length;
else
    return 0;
}