串的匹配 (Brute - Force 算法)

● 模式匹配

        • 设有主串 s 和子串  t , 子串 t 的定位就是要在主串 s 中找到一个与子串 t 相等的子串 . 

        • 通常我们把主串 s 称为目标串 , 把子串 t 称为模式串 , 定位也称作模式匹配

●模式匹配结果

        • 模式匹配成功 : 在目标串 s 中找到一个模式串 t

        • 模式匹配不成功 : 目标串 s 中不存在模式串 t

例如 : 

        s : This is his hat . It is historical.

        t : his

---

我们需要在 s 中找到 和 t 相同的串 的位置

其实串的匹配问题 , 在生活中很常见

比如 :

●网络安全:

        我们电脑里存放了一段病毒文件 , 我们不可能人工地去一个一个对比 , 这是很耗费时间的  , 我们需要拿着病毒文件 , 和 系统文件作对比 , 逐个去对比 ,找出病毒位置

●生物信息处理:

        侦破刑事案件的指纹识别 , 我们将犯罪嫌疑人的指纹 , 和提前录入数据库里面的指纹 , 进行匹配 . 帮助我们找到相应的犯罪嫌疑人的信息

● 语音识别:

        语音识别 ,把语音转换成数字 ,和 数据库里面的语言代码进行匹配, 这些都涉及到串的匹配. 

下面我们首先介绍一个最简单的算法 , 进行模式匹配  

● Brute - Force 算法

          • Brute - Force , BF 算法, 亦称简单匹配算法

         • 基本思路:

                •  从目标串 s 第一个字符开始 和 模式串 t 的第一个字符比较  , 若相等 , 则继续逐个比较后续字符 

                • 若不相等 , 则 从 s 的第二个字符 , 再次重新和模式串 t 第一个字符进行比较 ,

                • 以此类推

                • 若从 目标串 s 的第 i 个字符开始 , 每个字符依次和模式串 t 的对应字符相等 , 则匹配成功 , 返回 t  在 s 中的位置 i ; 否则 ,当我们遍历完了 串 s ,也没有匹配成功 , 代表匹配失败 ,函数返回 -1. 

---

第一次比较:  逐个比较 ,比较到第四个字符 , 不符合 , 我们就把 串 t 往后移动对比  

---

 

 第二次 : 我们再次从 t 开始和 s 的第二个字符匹配对比 , 比较到 t 的第四个字符 , 不符合 , 串t

继续 和 s 的第三个字符开始比较

---

 第三次 :  我们逐个比较 s 和 t 字符 , 匹配成功 , 返回 串 t 第一个字符 在 s 中的位置

---

上面是机器的模拟对比 , 我们可以拿两个纸片 , s固定 , 拿着 t ,从开头开始对比 , 不匹配,就后移一位 , 然后 再进行对比匹配 

下面进行代码实操 :

设置两个串  s  和  t

 

---

逐个进行对比 , 如果不同,则 串 t 向后移动 , 从串 t 开头和 串 s 第二个元素对齐,逐个遍历 ,总能找出答案 , 符合,或者不符合

 假如前四个有一个不符合 , 就从串 s 的第二个元素开始 ,和 串 t 进行逐个对比 , 以此类推

---

---

如果 , 串 t 的指针位序 ,能达到 串 t 的长度,则代表已经找到符合的串 ,跳出

如果 , 串 s 已经遍历完了 ,则也跳出 , 表示无符合的子串 

//传入两个串 s 和 t
int index(SqString s , SqString t)
{
	//下面我们定义, 每次开始重新对比时, 指向两个串的指针
	//初始都是0
	int i=0;	//指向 s 串每次开始对比的位序
	int i_1 = 0;	//每次对比 ,串 s 的计数器
	int j = 0;	//指向 t 串每次对比的位序
 
	//开始循环对比
	while((i+i_1)
	{
		//此时的 i ,j ,是初始的指针,我们还可以当作计数器, 来指向串元素
		//如果串 s 第i个元素 和 串 t 第 j 个元素相等, 则继续比较下一个
		if(s.data[i+i_1] == t.data[j])
		{
			i_1++;
			j++;
		}
		//如果不相同,就像我们图示那样,  串 s 重新开始对比的数组位序加一
		//此时串 t 也需要重新进行对比,计数器也置成0
		else
		{
			i++;
			j=0;
		}
 
	}
	//当我们的 j>=s.length的时候,跳出的时候,说明我们的串 t 已经判断完了,找到了符合的子串
	//我们返回其在串 s 中,刚开始的位序就行了
	if(j>=t.length)
	{
		//我们的 i ,就是每次重新遍历的 串 s的位序
		return (i);
	}
	else
	{
		//找不到或找不齐返回-1,表示没找到
		return (-1);
	}	
}

● 算法分析

• 最好情况复杂度: O(m)
        •目标串的前 m 个字符正好等于模式串的m个字符
    • 最坏情况复杂度 : O(n*m)
        • 每次到最后一个字符,才发现不匹配,这时再倒回去
            进行比较
        • 计数关系 : m*(n-m)

● 算法评价

• 这个算法简单 , 易于理解,但效率不高
    • 当m 小于 5时, 几乎是最好的,但是数字越多,复杂度剧增

● 算法的改进方案

● 为什么我们感觉复杂度增加 
        •因为我们每次都是匹配到不同的字符 ,都是对串 s 的开始字符,进行逐步加一,然后再让s和 t 进行从头对比
    ● 有些情况, 我们串 t 的每个字符都不相同, 我们对比之后 , 这一串对比的,就应该抛弃了,
        串s开始比较的字符就应该跳过 t的字符串长度的字符 ,
        再进行重新比较,我们下一步针对这个问题进行具体分析