1. 串
串的定义:
串是由零个或多个字符组成的有限序列，又名叫字符串。- 串是一种内容受限制的线性表，其特殊性体现在数据元素是一个字符。
零个字符的串，称为
空串，其长度为零。
由一个或多个空格组成的串，称为空格串，其长度为空格字符的个数。
通常称字符在序列中的序号为该字符在串中的位置。
(1) 串的比较
给定两个串，s = "a1a2.....an"，t="b1b2....bm"，当满足以下条件之一时，s<t。
- n<m，且ai = bi（i=1,2,.....,n）。例如，s="hap"，t="happy"，就有s<t。
- 存在某个k<=min(m,n)，使得ai = bi（i=1,2,.....,k-1）,ak < bk。例如，s="happen"，t="happy"，因为两串前4个字母均相同，而两串第5个字母（k值）, e 的ASCII码是101，而 y 的ASCII码是121，显然 e < y，所以s<t。
(2) 串的存储结构
1. 串的顺序存储
用一组地址连续的存储单元来存储串中的字符序列。一般用定长数组为每个定义的串变量分配一个固定长度的存储区。这样的存储方式存在问题，因为定长，在字符串操作时候，比如连接、插入新串、替换等操作时，都可能使串序列的长度超过了数组的长度MaxSize。
//串的定长顺序存储结构
#define MAXLEN 255
typedef struct {
char ch[MAXLEN+1]; //存储串的一维数组
int length;//串的当前长度
}SString;
堆（Heap）的自有存储区，可为每一个新产生的串动态分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址。
//串的堆式顺序存储结构
typedef struct {
char *ch;//若是非空串，则按串长分配存储区，否则ch为NULL
int length;//串的当前长度。
}HString;
2.串的链式存储
与线性表相似，但因为串中每个元素都是一个字符，如果用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满，可用“#”或其他非串值字符补全。
这里后面算法描述当中所有顺序存储的字符串都是从下标为1的数组分量开始存储的，下标为0的分量闲置不用。
//串的链式存储结构
# define CHUNSIZE 80 //可由用户定义的快大小
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct {
Chunk *head,*tail;//串的头和尾指针
int length;//串的当前长度
}LString;
(3) 串的模式匹配算法
- 子串的定位运算通常称为串的模式匹配或串的匹配。
- 串的模式匹配设有两个字符子串，设S为主串，也称正文串，设T为子串，也称为模式。在主串中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串的第一个字符在主串S中出现的位置。
1. BF算法
模式匹配不一定从主串的第一个位置开始，可以指定主串中查找的起始位置pos。
算法步骤：
- 分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置，i的初始值为pos，j的初始值为1。
- 若果两个串均未比较到串尾，即i和j均分别小于等于S和T的长度时，则循环执行以下操作：
- S.ch[i]和T.ch[j]比较，若相等，则i和j分别指示串中下个位置，继续比较后续字符。
- 若不等，指针后退重新开始匹配，从主串的下一个字符（
i＝ i-j＋2) =>{ i ＝ i -(j-1)+1}起重新和模式的第一个字符（j=1）匹配。
- 如果j>T.length,说明模式T中的每一个字符依次和主串S中一个连续的字符序列相等，则匹配成功，返回和模式T中第一个字符串相等的字符在主串S中的序号。（i-T.length）否则不成功，返回0。
int Index_BF(SString S,SString T,int pos)
{
int i = pos; //初始化
int j = 1;
while(i<S.length && j<T.length) // 两个串均未比较到串尾
{
if(S.ch[i] == T.ch[j]) { ++i;++j;}//继续比较后继字符
else {i=i-j+2;j=1;}//指针后退重新开始匹配
}
if(j > T.length) return i-T.length; //匹配成功
else return 0;//匹配失败
}
BF算法时间复杂度分析如下：
- 最好情况下，每趟不成功的匹配都发生在模式串的第一个字符与主串中相应字符的比较。
例如：
S = "aaaaaba";
T = "ba"
设主串长度为n,子串的长度为m，假设从主串的第i个位置开始与模式匹配成功，则在前i-1t趟匹配中字符总共比较i-1次，若第i趟成功的字符比较次数为m，则总比较次数为i-1+m。相对与成功匹配主串，其起始位置由1到n-m+1,假定这n-m+1个起始位置上匹配成功的概率相等，则最好的情况下匹配成功的平均比较次数为：
即最好的情况下的平均时间复杂度为O(n+m)
- 最坏的情况下，每趟不成功的匹配都发生在模式串的最后一个字符与主串中相应字符的比较。
例如：
S = "aaaaab"
T = "aab"
假设从主串的第i个位置开始与模式匹配成功，则前i-1趟匹配中字符总共比较了(i-1)＊m次，若第i趟成功的比较次数为m，则总共比较次数im。因此最坏情况下匹配成功的平均比较次数为：
即最坏的情况下平均时间复杂度为O(nm)。
2. KMP算法
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。
当主串的第i个字符与模式串中第j个字符匹配失败时，主串的第i个字符（i指针不回溯）与模式串的第k（k<j ）个字符比较，则模式中的前k-1个字符串必需满足下列关系式：
若令next[j] ＝ k,则next[j]表明模式中第j个字符与主串相应字符失配时，在模式中需要重新和主串字符进行比较的字符位置，由此引出模式串中next函数的定义：
next数组值推导
如果前后缀一个字符相等，k值是2，两个字符相等k值是3，n个字符相等k值就是n+1。
KMP 算法描述
void get_next(String T, int next[])
{
int i,j;
i=1;
j=0;
next[1]=0;
while (i<T.length)
{
if(j==0 || T[i]== T[j])/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
{
++i;
++j;
next[i] = j;
}
else j= next[j]; /* 若字符不相同，则j值回溯 */
}
}
int Index_KMP(String S, String T, int pos) {
int i = pos; /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
int j = 1; /* j用于子串T中当前位置下标值 */
int next[255]; /* 定义一next数组 */
get_next(T, next); /* 对串T作分析，得到next数组 */
while (i <= S.length && j <= T.length) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
{
if (j==0 || S.ch[i] == T.ch[j]) /* 两字母相等则继续，与朴素算法增加了j=0判断 */
{
++i; ++j;
}
else
{ /* 指针后退重新开始匹配 */
j = next[j];/* j退回合适的位置，i值不变 */
}
}
if (j > T.length) return i-T.length; //匹配成功
else return 0;//匹配失败
}
