4 串(string)

Wu Jun 2019-05-23 19:48:37
01 数据结构与算法 > 数据结构 > 01 数据结构

1 基本概念

字符编码
串的比较

2 存储结构

串的顺序存储结构

一般是用定长数组来定义,存在一个预定义的最大串长度。

对于超出预定义的最大串长度的计算,串值的存储空间可在程序执行过程中动态分配

串的链式存储结构

与线性表相似,但为了不浪费空间,一个结点可存放多个字符,最后一个结点未占满时用"#"或其它非串值字符不全。

串的链式存储结构除了在连接串与串操作时有一定方便之外,总的来说不如顺序存储灵活 ,性能也不如顺序存储结构好。

3 字符串匹配

1)KMP 模式匹配算法

Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”。减少了不必要的比较,比朴素的模式匹配算法效率提高了很多。

算法流程

假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

next 数组代表当前字符之前的字符串中,有多大长度的相同前缀后缀。

计算next 数组

next[j] = k 代表p[j] 之前的模式串子串中,有长度为k 的相同前缀和后缀

//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀,p[j]表示后缀  
		if (k == -1 || p[j] == p[k])
		{
			++j;
			++k;
			//较之前next数组求法,改动在下面4行
			if (p[j] != p[k])
				next[j] = k;   //之前只有这一行
			else
				//因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
				next[j] = next[k];
		}
		else
		{
			k = next[k];
		}
	}
}
KMP代码
int KmpSearch(char* s, char* p)
{
	int i = 0;
	int j = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	while (i < sLen && j < pLen)
	{
		//①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++    
		if (j == -1 || s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			//②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]    
			//next[j]即为j所对应的next值      
			j = next[j];
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}
KMP的时间复杂度分析

文本串的长度为n,模式串的长度为m,匹配过程为O(n),计算next为O(m),KMP的整体时间复杂度为O(m + n)。

2)BM算法(更快)

Boyer-Moore算法,简称BM算法。

从模式串的尾部开始匹配,且拥有在最坏情况下O(N)的时间复杂度。

BM算法定义了两个规则:

3)Sunday算法(最快)

Sunday算法是从前往后匹配,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。