数据结构-串

ADT String{

        数据对象：D = {aᵢ | aᵢ∈CharacterSet, i = 1,2,...,n,n >= 0}

数据关系：R = {<aᵢ₋₁,aᵢ> | aᵢ₋₁,aᵢ∈D,i = 1,2,...,n}

基本操作：

        StrAssign(T, *chars)：生成一个其值等于字符串常量chars 的串T
StrCopy(T, S)：串S存在，由串S复制给T
ClearString(S)：将串清空
StringEmpty(S)：判断是否为空
StrLength(S)：返回串的元素个数
StrCompare(S, T)：若S>T，返回值>0；若S=T，返回值等于0；若S<T，返回值<0；
Concat(T, S1, S2)：用T返回由S1和S2连接形成的新串
SubString(Sub, S, pos, len)：串S存在。1<= pos <= StrLength(S)，且0 <= len <= StrLength(S) - pos + 1，用Sub返回串S的第pos个字符起长度为len的子串

        Index(S, T, pos)：串S、T存在，T是非空串，1 <= pos <= StrLength(S)。若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符出现之后第一次出现的位置，否则返回0

        Replace(S, T, V)：串S,T,V存在，T是非空串。用V替代主串S中出现所有与T相等的不重叠的子串
StrInsert(S, pos, T)：串S，T存在，1 <= pos <= StrLength(S) + 1。在串S的第pos个字符前插入串T
StrDelete(S, pos, len)：串S存在，1 <= pos <= StrLength(S) -len + 1。从串S中删除第pos个字符起长度为len的子串
}ADT String

串的顺序存储结构

#define MAXLEN 255

typedef struct
{
	// +1，多分配一个存储空间，为了数组下标从1开始，下标0处闲置不用
	char ch[MAXLEN + 1];  // 字符串的一维数组
	int length;  // 串的当前长度
}SString;

串的链式存储结构

优点：操作方便
缺点：存储密度低（1/（1 + 4 = 0.2）
- 存储一个字符需要1个字节，但存储一个地址需要4个字节，所以要存储一个数据结点需要5个字节
- 存储密度 = 数据本身所占用的空间 / 数据结点总共占用的空间

可将多个字符存放在一个结点中，以克服其缺点

存储密度：4 /（4 + 4）= 0.5

一个大格子叫作“块”

块链结构

#define CHUNKSIZE 80  // 块的大小可由用户定义
typedef struct Chunk
{
	char ch[CHUNKSIZE];
	struct Chunk* next;
}Chunk;

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

串的模式匹配算法

算法目的：确定主串中所含子串（又称模式串）第一次出现的位置（定位）

算法应用：搜索引擎、拼写检查、语言翻译、数据压缩

算法种类：

BF算法（Brute-Force，又称古典的、经典的、朴素的、穷举的）

KMP算法（特点：速度快）

BF算法（例：Index(S, T, pos)）

Brute-Force简称BF算法，亦称简单匹配算法。采用穷举的思路
回溯
- T从位置1移动到 j，移动了 j - 1 个长度
- S现在的位置是 i，移动的长度也是 j - 1，用现在的位置 i 减去移动的长度，再 +1 就是下一个位置
- i - (j - 1) + 1，即，i - j +2

BF算法设计思想

Index(S, T, pos)
将主串的第pos个字符和模式串的第一个字符比较
- 若相等，继续逐个比较后续字符
- 若不等，从主串的下一字符起（i = i-j+2），重新与模式串的第一个字符比较
直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的符号，即匹配成功。否则匹配失败，返回0

BF算法实现O(n*m）

int index_BF(SString S, SString T, int pos)
{
    // i表示主串S中当前的位置
	int i = pos;

    // j表示子串T中当前位置
	int 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

理解

例1：模式串超出了主串的范围，判定匹配失败

找到不匹配处，在不匹配处的左侧，主串和模式串完全匹配

模式串左右两端两个子串完全匹配，称之为模式串的公共前后缀

前缀要包含第一个字符，后缀要包含不匹配处前一个字符

（如果模式串中有多对公共前后缀，取最长的一对）

直接往前移动模式串，让其公共前后缀里的前缀直接移动到后缀所在位置

这样可以保证当前比较指针所在的位置左侧的串，上下匹配

继续往后移动，有遇到不匹配处，在前面找公共前后缀

移动模式串，使得前缀与原来后缀位置重合

但这时候，模式串超出了主串的范围，判定匹配失败，主串中不含有和模式串相同的子串

例2：找最长公共前后缀，最后匹配成功

找到不匹配处，然后寻找公共前后缀

公共前后缀1

公共前后缀2

发现有两个公共前后缀，取最长的公共前后缀2

移动后，又找到不匹配处，然后找最长公共前后缀

最后匹配成功

例3：只研究模式串

我们在把公共前缀移动到公共后缀位置的时候，不需要主串。所以，对于KMP算法，只研究模式串就够了
用模式串的相关信息就可以和任何的主串进行匹配

模式串一般从数组下标1开始存储的，0位置什么都不存

假设1号位，模式串与主串不匹配

这时候，1号位与主串下一位比较

假设2号位，模式串与主串不匹配

模式串移动，指针左边的子串长度，就是公共前后缀的长度

此处，公共前后缀长度为0，所以移动之后，指针左边的子串长度为0

这时候，1号位与主串当前位比较

假设3号位，模式串与主串不匹配

因为公共前后缀长度为0，所以和2号位情况一样

这时候，1号位与主串当前位比较

假设4号位，模式串与主串不匹配

2号位与主串当前位比较

假设5号位，模式串与主串不匹配

找到最长公共前后缀

移动模式串

这时候，模式串的3号位与主串当前位比较

假设6号位，模式串与主串不匹配

找到最长公共前后缀

移动模式串

这时候，4号位与主串当前未进行比较

总结

在1号位时不匹配时，模式串1号位与主串下一位比较
其余位，如果最长公共前后缀长度为n，我们得到模式串n+1号位与主串当前位进行比较

计算当前要匹配的模式串T的next数组的KMP算法

该数组用于，在不匹配时，指导搜索指针应该移动到的位置。next 数组的每个元素 next[k] 表示字符串 T 的前 k 个字符中最长的相同前后缀的长度
我们定义next[j]，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置
- 当j = 1时，next[j] = 0
- 其余情况，next[j]都等于最长公共前后缀n+1

// 这串代码的目的是为了计算出当前要匹配的串T的next数组
void get_next(SString  T, int* next)
{
	int i = 1;
	int j = 0;
	next[1] = 0;

	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
		{
			// 若字符不同，则j值回溯
			j = next[j];
		}
	}
}

j == 0 || T.ch[i] == T.ch[j]

j == 0：如果 j 为 0，意味着我们已经回溯到了模式串T 的开始，没有匹配的前缀，所以 i 应该继续向右移动
T.ch[i] == T.ch[j]：如果当前字符 T.ch[i] 与模式串中的位置 j 上的字符相同，那么 i 和 j 都可以向右移动

next[i] = j

next[i] 表示在模式串中，直到位置 i（不包括当前位置 i）为止的子串中，最长公共前后缀的长度
j 是当前正在比较的模式串中的位置，它表示在位置 i 之前的子串中，我们找到的最长公共前后缀的长度

`j = next[j]`

如果当前字符不匹配（T.ch[i] != T.ch[j]），则 j 需要回溯到 next[j] 指定的位置
因为 next[j] 存储了在 j 之前的位置中，最长的相同前后缀的长度
这意味着我们可以安全地跳到那个位置，而不需要回溯到字符串的开始

Index_KMP算法O(m+n)

返回子串T在主串S中第pos个字符之后的位置

int Index_KMP(SString S, SString T, int pos)
{
	// i表示主串S当前位置下标值
	int i = pos;

	// j表示子串T当前位置下标值
	int j = 1;

	int next[255];

	// 对模式串T分析，得到next数组
	get_next(T, next);

	while (i <= S.length && j <= T.length)
	{
        /*
        如果模式串的当前位置是开始（j == 0）
        或者当前正在比较的字符相同（S.ch[i] == T[j]）
        那么我们可以继续匹配过程，将 i 和 j 都增加 1
        */
		if (j == 0 || S.ch[i] == T[j])
		{
			++i;
			++j;
		}
		else
		{
			// i不变，j后退
			j = next[j];
		}
		// 匹配成功
		if (j > T.length)return i - T.length;
		else return 0;
	}
}

next函数的改进

这个例子进行了多次比对

但实际上，只要看比对的字符前面有没有一样的，如果有一样的，就不需要推到那个位置了

根据next值求nextval值的方法

get_nextval

void get_nextval(SString  T, int* nextval)
{
	int i = 1;
	int j = 0;
	nextval[1] = 0;

	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			++i;
			++j;
			
			/*
			若当前字符与前缀字符不同
			则当前的j为nextval在i位置的值
			*/
			if (T.ch[i] != T.ch[j]) 
			{
				nextval[i] = j;
			}
			else
			{
				/*
				如果当前字符与前缀字符相同，
				则将前缀字符的nextval值，
				赋值给nextval在I位置的值
				*/
				nextval[i] = nextval[j];
			}
		}
		else
		{
			// 若字符不同，则j值回溯
			j = nextval[j];
		}
	}
}

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。