---

串的三要素

逻辑结构（定义）

串，即字符串（String）是由零个或多个字符组成的有限序列，串中字符的个数 n 称为串的长度。n=0 时的串称为空串。

串是一个特殊的线性表，数据元素之间呈线性关系

子串：串中任意个连续的字符组成的子序列
主串：包含子串的串
字符在主串中的位置：字符在串中的序号
子串在主串中的位置：子串的第一个字符在主串中的位置

数据的运算（基本操作）

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

存储结构（物理结构）

顺序串（顺序存储）

顺序串的定义
静态分配

#define MAXLEN 255    // 预定义最大串长为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;

求子串

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.ch[i-pos+1] = S.ch[i];}Sub.length = len;return true;
}

比较操作

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;
} 

定位操作

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相等的子串
}

链式串（链式存储）

存储密度低，每个字符1B，每个指针4B

typedef struct StringNode{char ch;  // 每一个结点存1个字符struct StringNode *next;  // 指针
}StringNode,*String;

提高存储密度

typedef struct StringNode{char ch[4];   // 每个结点存多个字符struct StringNode *next;
}StringNode,*String;

字符串模式匹配

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

两种模式匹配的算法
1、朴素模式匹配算法
2、KMP算法

朴素模式匹配算法

主串长度为n，模式串长度为m
将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止
最多对比 n-m+1个子串

Index(S,T) 定位操作就是利用了朴素模式匹配算法原理

通过数组下标实现朴素模式匹配算法

int Index(SString S,SString T){int i = 1, 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;elsereturn 0;
}

设主串长度为n，模式串长度为m，则时间复杂度 O(nm)

朴素模式匹配算法的缺点：当某些子串与模式能部分匹配时，主串的扫描指针经常回溯，导致时间开销增加。

KMP算法

KMP算法：利用next数组进行匹配，减少回溯

int Index_KMP(SString S,SString T,int next[]){int i = 1, j = 1;whlie(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;  // 匹配成功elsereturn 0;
} 

代码中的next数组是：当模式串的第j个字符匹配失败时，令模式串跳到next【j】再继续匹配

求模式串的next数组

串的前缀：包含第一个字符，且不包含最后一个字符的子串
串的后缀：包含最后一个字符，且不包含第一个字符的子串

如 'abababcdef'
前缀：'abababcde'
后缀：'bababcdef'

当第j个字符匹配失败，由前 1~j-1个字符组成的串记为S，则next[j] = S的最长相等前后缀长度加1，
注意：next[1] = 0 , next[2] = 1

模式串：'ababaa'
当j=1时，next[1] = 0;
当j=2时，next[2] = 1;
当j=3时，S：ab, 前缀：a, 后缀：b, 前缀后缀相等长度为0 , next[3] = 0+1 = 1;
当j=4时，S：aba, 前缀：ab, 后缀：ba, 前缀后缀相等长度为0 , next[4] = 0+1 = 1;
当j=5时，S：abab, 前缀：aba, 后缀：bab, 前缀后缀相等最长串为ab，长度为2 , next[5] = 2+1 = 3;
当j=6时，S：ababa, 前缀：abab, 后缀：baba, 前缀后缀相等最长串为aba，长度为3 , next[6] = 3+1 = 4;所以得
序号j	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4

代码如下

void get_next(SString T, int next[]){int i=1,j=0;next[1]=0;while(i<T.length){if(j==0 || T.ch[i] == T.ch[j]){++i;j++;// 若pi=pj,则next[j+1]=next[j]+1next[i] = j;} else {j = next[j];}}
}

KMP算法完整代码时间复杂度 O(n+m)

int Index_KMP(SString S,SString T){int i = 1, j = 1;int next[T.length+1];get_next(T,next);whlie(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;  // 匹配成功elsereturn 0;
} 

KMP算法的进一步优化

对于KMP算法色优化实际上是优化next数组，将next数组优化为nextval数组

例如上面的next数组
序号j		1	2	3	4	5	6
模式串		a	b	a	b	a	a
next[j]		0	1	1	2	3	4
nextval[j]	0	1	0	1	0	4//求nextval
netval[1] = 0;
for(int j=2; j<=T.length;mj++){if(T.ch[next[j]] == T.ch[j])nextval[j] = nextval[next[j]];elsenextval[j] = next[j];
}