串基本概念：串是由零个或者多个字符组成的有限序列，一半记作S='a1,a2,a3,a4.......'（n>=0，串的长度）

1.S == 串的名字     n ==  串当中字符串的个数，称为串的长度。

串的常用术语

1.空串（null string）：长度为零的串，它不包含任何字符。

2.空格串(black string) :任由一个或多个空格组成的串，长度大于等于1

3.子串（sub string）:串中任意个连续字符的组成的子序列称为该串的“子串”

4.主串（master string):包含子串的串相应的称为“主串”，因此子串是主串的一部分。

5.前缀子串（prefix sub string）：S的前缀子串是一个子串U,记作U = 'a1,.....ab'(1<=b<=n)，当1<=b

6.后缀子串（suffix sub string）：S的后缀子串是一个子串U,记作U = 'an-b-1....an'(1<=b<=n)，当1<=b

eg.S='abccset',S的前缀子串是‘a’,'ab','abc','abcc','abccs','abccse'。S的后缀子串是‘t’,'et','set','cset','ccset','bccset'。

7.位置:通过将字符在串中的序号，称为该字符在串中的“位置”。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

8.串相等：当且仅当两个串的值相等的时候，则称两个串的数值相等。条件：长度相等以及位置必须相等

9.模式匹配：确定子串在主串的某个位置开始后，在主串中首次出现的位置的运算。主串=="目标串"，子串==“格式串”。

eg. 串A = “abcaabsbcas”，串B = "bca",从第一个位置开始，匹配的运算结果是2，从第四个位置开始的运算结果是8。

串的基本运算

 1.strInsert(S,pos ,T)

设S='chater',T=‘rac’,运行StrInsert(S,4,T),S='character'

2.strDelete(S.pos,len)

设S='chapter',运行StrDelete(S,5,3),则S='chap'

3.StrCat(S,T)

设串S='man',运行Strcat(S,'kind'),则S='mankind'

4.Substring(T,S,pos,len)

eg.设串S='commander',运行SubString(Sub1,S,4,3),则Sub1='man'。

5.StrIndex(S,pos,T)

设S='abcaabcaaabc',T='bca',运行StrIndex(S,1,T),返回2，运行StrIndex(S,4,T)，返回值是 6。

6.StrReplace(S,T,V)

eg.设S='abcaabcaaabca',T='bca',若V='x',则S='axaxaax',若V='bc',则S='abcancaabc'

串的存储结构以及实现

 定义顺序串

1.定长顺序串存储结构

#define MAXSIZE 50
typedef struct
{char ch[MAXSIZE+1];       //0号元素不使用（浪费一个空间），每个分量存储一个字符。int len;
}SString;

 串的实际长度可以在MAXSIZE范围内随意变动，超过范围的会舍去，称为“截断”。

2.定长串的基本操作实现

插入：三种情况

int SStrInsert(SString *S,int pos,const SSttring T)
{int i;if(pos<1 || pos >S->len+1)return 0;//插入的子串没有超过最大值且主串不需要舍弃 if(S->len + T.len<=MAXSIZE){for(i = S->len+T.len;i>=pos+T.len;i--){S->ch[i] = S->ch[i-T.len];}for(i = pos;ilen+T.len;i++){S->ch[i] = S->ch[i-pos+1]}S->len = S->len + T.len;}//子串可以完全插入，但是主串需要舍弃一部分 else if(pos+T.len<=MAXSIZE){for(i = MAXSIZE;i>=pos+T.len;i--){S->ch[i] = S->ch[i-T.len]}for(i = pos;ilen+T.len;i++){S->ch[i] = S->ch[i-pos+1]}S->len = MAXSIZE;} //子串插入在任意位置，都超出了最大范围 else{for(i = pos ;i<=MAXSIZE;i++){S->ch[i] = T.ch[i-pos+1]}S->len = MAXSIZE;}return 1;
}

删除函数：

int SStrDelete(SSting *S,int pos,int len)
{int i = 1;if(pos<1 || pos>S->len || len<0 || len>S->len-pos+1){return 0;}for(i = pos;ilen-len;i++){s->ch[i] =  S->ch[i+len]; }return 1;
} 

串的连接

1.连接后串长小于等于MaxSize,则直接连接在第一个串的后面。

2.连接后，当串长大于MaxSize,且原始串的长度小于MaxSize，则待连接串则会舍弃一部分，当原始串长==MaxSize，则将待连接串全部进行舍弃。

int SStrCat(SSting *S,const SString T)
{int i = 1;if(S->len+T.len<=MaxSize){for(i = S->len;i<=S->len+T.len;i++){S->ch[i] = S.ch[i-S->len];}S->len = S->len+T.len;}else if(S->lenlen;i<=MaxSize;i++){S->ch[i] = S->ch[i-S->len]	}	S->len = MaxSize;}elsereturn 0;
}

堆串（相较于定长的顺序串，堆串可以动态的分配内存空间，这样可以保证不会出现截断的情况）

1.串的初始化 

void HSrInit(HString *S)
{S->ch = NULL;S->len = 0;
}HString;

2.串的赋值操作

int HstrAssign(HString  *S,const char * chars)
{int i = 0;while(char[i] != '\0')i++;S->len = i;if(0 != S->len){if(S->ch != NULL)free(S->ch);S->ch = (char *)malloc((S->len + 1) * sizeof(char));if(NULL == S->ch)return 0;for(i = 1;i<=S->len;i++){S->ch[i] = chars[i-1];}elseS->ch = NULL;return 1;}	
} 

3.串的插入

int HStrInsert(HString *S,int pos,const HString T)
{int i;char * temp;if(pos>S->len || pos<1)return 0;temp = (char *)malloc(sizeof(S->len+T.len + 1)*sizeof(char));if(temp == NULL)return 0;for(i = 0;ich[i];for(i = pos;ich[i-pos+1];for(i = pos+T.len;i<=S->len+T.len;i++)temp[i] = S->ch[i-T.len];free(S->ch)S->ch = temp;S->len+=T.len;return 1; 
}

4.串的删除

int HStrDelete(HString *S,int pos,int len)
{int i;char *temp;if(len<0 || pos<1 || pos>S->len-len+1)return 0;temp = (char *)malloc(sizeof(S->len-len+1) * sizeof(char));if(NULL == temp)return 0;for(i = 0;ich[i];for(i = pos;i<=S->len-len;i++)temp[i] = S->ch[i+len];free(S->ch);S->ch = temp;S->len-=len;return 1;
}

5.串的连接

int HStrCat(HString * S,const HString)
{int i = 1;S->ch = (char *)malloc(S->ch,(S->len +T.len +1)*sizeof(char));if(NULL == S->ch)return 0;for(i = S->len+1;i<=T.len+S->len;i++)S->ch[i] = T.ch[i-S->len];S->len = S->len + T.len;return 1;
}

块链串（链表的每一个结点存放一个字符或者多个字符，每个结点称为块，整个链表称为“块链结构”）

 块大小：块链表存放字符的个数

当块的大小 == 1的时候，增删改查的方法和单链表一样，因为只有一个数据域和一个指针域，但当块的大小 ≠ 1的时候，则需要进行结点的拆分和合并....

存储密度：存储密度 = 串值所占的存储位 / 实际分配的存储位

串的模式匹配

1.BF模式匹配算法 

思路：从主串的第一个字符开始进行匹配，当主串和子串的字符不相同的时候，就回溯到开始字符的下一个字符，重新开始进行匹配，知道找到为止

int indedx(SString S,int pos,SString T)
{int i = pos,j = 1;while(i<=S.len && j<=T.len){if(S.ch[i] == T.ch[j])i++,j++;else{i = i-j+2;    //返回到起始比较字符的下一位，重新开始判断j = 1;}}if(j > T.len)return i-T.len;elsereturn 0;
}

2.KMP模式匹配算法

思路：相对于暴力索引求解，KMP的时间复杂度大大降低，开始都是和BF算法一样，一个一个字符进行匹配，但当主串和子串的字符不相等的时候，不再是回到主串中开始比较字符的下一位，而是进行一个“子串向后移动最长前后缀相等子串长度”，最后找到对应的字符串。（详细介绍：数据结构KMP算法配图详解（超详细）_哈顿之光的博客-CSDN博客_kmp算法难吗是什么级别）

这里需要好好理解一下next数组的作用（记录当前字符的前面的最长前后缀相等的字符串）

首先将模式串的每一个字符对应的next的数值求出来

eg. "ABCABCKO"

 这样就得到了当前每一个字符对应的next数组的数值。

void Get_Next(SString T,int next[])
{int j = 1,k = 0;next[1] = 0;while(j < T.len){if(k == 0 || T.ch[j] == T.ch[k]){++j;++k;next[j] = k;}elsek = next[k];printf("%d \n",next[k]);}
}

int KMPIndex(SqString s,SqString t)  //KMP
{int next[MaxSize],i=0,j=0;GetNext(t,next);while (i=t.length)return(i-t.length);  	else  return(-1);        		
}