串

**串(String)**：零个或多个任意字符组成的有限序列
内容受限制的线性表(只能是字符)
S = “a1a2a3 … an”(n >= 0)
串名 = “串值”
n:串长
串的几个术语
子串：一个串中任意个连续的字符组成的子序列(含空串)称为该串的子串
    真子串：不包含自身的所有子串
主串：包含子串的串相应地称为主串

字符位置：字符在序列中的序号为该字符在串中的位置
子串位置：子串第一个字符在主串中的位置

空格串：由一个或多个空格组成的串，与空串不同
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相等时，这两个串才是相等的(所有空串是相等的)

应用案例
串的应用非常广泛，计算机上的非数值处理的对象大部分是字符串数据，例如：文字编辑、符号处理、各种信息处理系统等等。
案例：病毒感染检测

串的类型定义、存储结构

串的顺序存储结构(常用)
逻辑关系直接映射到物理位置
(后面的算法用顺序存储结构实现)

顺序串的结构类型

#define MAXLEN 255
typedef struct{
	//存储串的一维数组 [0]-[MAXLEN]
	//为了操作方便，第一个位置不存
	char ch[MAXLEN + 1]; 
	int length; //串的当前已用长度
}SString;

串的链式存储结构 — 块链结构

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

#define CHUNKSIZE 80
//块
typedef struct Chunk{
	char ch[CHUNKSIZE];
	struct Chunk *next;
}Chunk;

//字符串的块链结构
typedef struct{
	Chunk *head,*tail; //串的头指针and尾指针
	int curlen; //串的当前长度
}LString; 

串的操作

串的模式匹配算法
算法的目的：
确定主串中所含子串(模式串)第一次出现的位置(定位)
算法应用：
搜索引擎、拼写检查、语言翻译、数据压缩
算法种类：
    BF算法(Brute-Force，又称古典的、经典的、朴素的、穷举的)
    KMP算法(特点：速度快)

BF算法

也称为简单匹配算法。采用穷举法的思路

匹配失败时：
i = i - (j-1) + 1 (回溯)
用现在i减去移动的长度i-(j-1),再 +1 就是下一个位置
即i=i-j+2
j = 1 (从头开始)

匹配成功：
返回 i - t.length = 3

时间复杂度：
最坏的情况下比较的次数：(n - m + 1)* m 次
O(n * m)

//找子串位置
int Index_BF(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算法

KMP算法是 D.E.Knuth、J.H.Morris 和 V.R.Pratt共同提出的，简称KMP算法

时间复杂度：O(n + m)

定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行比较的字符的位置

KMP算法

int Index_KMP(SString S,SString T,int pos){
	i = pos;
	j = 1;
	while(i < S.length && j < T.length){
		if(j == 0 || S.ch[i] == T.ch[j]){
			i++;
			j++;
		}else{
			//i不变 j后退
			j = next[j] //j == 0时要i向后一位
		}
	}

	if(j > T.length){
		//匹配成功
		return i-T.length; 
	}else{
		//匹配不成功
		return 0;
	}
	
}

得到next[j]

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

next函数改进：

改进后KMP算法

int Index_KMP(SString S,SString T,int pos){
	i = pos;
	j = 1;
	while(i < S.length && j < T.length){
		if(j == 0 || S.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] 
		}
	}

	if(j > T.length){
		//匹配成功
		return i-T.length; 
	}else{
		//匹配不成功
		return 0;
	}
	
}

Donate