第三章-串

定义：由零个或多个字符组成的有限序列。记为S=‘a1a2······an’，n=0时称为空串。
串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。
当两个串的长度相等且每个对应位置的字符都相等时，称两个串是相等的。
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。

串的存储结构

定长顺序存储表示

用一组地址连续的存储单元来存储串值的字符序列。

#define MAXLEN 255    //预定义最大串长为255
typedef struct{
	char ch[MAXLEN];  //每个分量存储一个字符
	int length;       //串的实际长度
}SString

串的实际长度只能小于或等于MAXLEN，超过预定义长度的串值会被舍去，称为截断.

堆分配存储表示

typedef struct{
	char *ch;     //按串长分配存储区，ch指向串的基地址
	int length;   //串的长度
}HString

基本操作

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

简单模式匹配

子串的定位操作通常称为串的模式匹配，他求的是子串（模式串）在主串中的位置，以下给出暴力匹配算法。

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;
	else return 0;
}

KMP算法

//得到部分匹配表next[]
void get_next(SString T,int next[]){
	int i=1,j=0;                     //i是字符串遍历索引；j是与后缀匹配长度的索引
	next[1]=0;
	while(i<T.length){
		if(j==0||T.ch[i] == T.ch[j]){//先评判前面是否存在匹配长度，不存在则i所指的位置的匹配长度j重新回到头部位置；若存在则继续评判该i位置元素是否与前面匹配成功的长度的位置j元素是否相等，如果相等，则i下一个元素的后缀匹配长度为j，但是部分匹配成功索引需要对该长度位置的下一个位置进行比对，所以next对应的元素应该为长度加1；不相等，则回到成功匹配长度位置所对应的next元素进行比对。
			++i;++j;
			next[i]=j;
		}else{
			j=next[j];
		}
	}
}

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

KMP算法时间复杂度为O(m+n),KMP算法仅在主串与子串有很多“部分匹配”是才显得比普通算法快得多

KMP算法优化

当相同字符在字符串中连续不间断出现很多次时，需要改进next数组，只需要添加多一个判断进行判断当前位置是否与匹配长度位置是否相等。

void get_nextval(SString T,int nextval[])
{
	int i=1;j=0;
	nextval[1]=0;
	while(i<T.length){
		if(j==0||T.ch[i]==T.ch[j]){
			++i;++j;
			if(T.ch[i]!=T.ch[j]) nextval[i]=j;
			else nextval[i]=nextval[j];
		}
		else{
			j=nextval[j];
		}
	}
}

XYX Blog