第四章-串

目录

存储方式

定长顺序存储表示

堆分配存储表示

串的基本操作

串的模式匹配

简单模式匹配算法

串的模式匹配算法——KMP算法

KMP算法的进一步优化 图4.7

手工计算next[ ]

---

存储方式

定长顺序存储表示

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

堆分配存储表示

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

串的基本操作

StrAssign(&T,chars);//赋值操作。把串T赋值为chars
StrCopy(&T,S);//复制操作。由串S复制得到串T
StrEmpty(S);//判空操作。若S为空串，则返回TRUE
StrCompare(S,T);//比较操作。若S>T，则返回值>0,若S=T，返回值=0,若S
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算法

普通模式匹配时间复杂度O(mn)，KMP算法时间复杂度O(m+n)。

KMP算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快得多，其主要优点是主串不回溯。

前缀：指除了最后一个字符以外，字符串的所有头部子串

后缀：指除第一个字符外，字符串的所有尾部子串

部分匹配值：字符串的前缀和后缀的最长相等前后缀长度

next[j]的含义：在子串的第 j 个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。

求next值Code：

void get_next(String T,int next[]){
	int i=1,j=0;
	next[1]=0;
	while(i
		if(j==0||T.ch[i]==T.ch[j]){
			++i,++j;
			next[i]=j;//若pi=pj,则next[j+1]=next[j]+1; 
		}
		else j=next[j];//否则令j=next[j]，循环继续 
	}
}

KMP的匹配算法Code：

int Index_KMP(String S,String T,int next[]){
	int i=1,j=1;
	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; 
}

KMP算法的进一步优化 图4.7

若模式串与主串出现不匹配（设此时的模式串字符为 ch），则需要将模式串 向右移动，若词根（最后一个字符）还和 字符ch 一样（此时匹配结果当然还是一样，必然失配，比较毫无意义），则还需要 继续向右移动... ，这就需要给出优化方案。👇

如果出现此情况，则需要再次递归，将next[j] 修正为next[ next[j] ],直至两者不相等为止，更新后的数组命名为nextval[ ]。

void get_nextval(String T,int nextval[]){
	int i=1,j=0;
	nextval[1]=0;
	while(i
		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];
	}
}

手工计算next[ ]

将子串（模式串）的部分匹配值写成数组形式，得到PM（Partial Match）表。

当子串与主串出现不匹配时，子串向右移动

右移位数 = 已匹配的字符数 - 对应的部分匹配值

Move = ( j - 1 ) - PM[ j-1]

由于每次匹配失败，要找前一个元素的部分匹配值，使用起来不方便，所以将PM表向右移一位。就得到next[ ]数组。

1->第一个元素用-1来填充，因为若是第一个元素匹配失败，则需要将子串向右移动一位，而不需要计算子串移动的位数

2->最后一个元素在右移的过程中溢出，因为原来的子串中，最后一个元素的部分匹配之是其下一个元素使用的，但显然已没有下一个元素，故可以舍去。

Move=( j-1)-next[j]

相当于子串的比较指针 j 回退到

j = j-Move = j- ( (j-1)-next[j] ) = next[j]+1

为了使公式更加简洁、计算简单，将next[ ]数组整体+1

最终得到子串指针变化公式 j=next[j]，在实际匹配过程中，子串在内存里是不会移动的，而是指针在变化。