蛮力法解决串匹配问题.doc

算法分析实验报告

蛮力法-串匹配问题

学生姓名：
专 业：
班 级：
学 号:
指导教师：

2017年6月12日
目录

一、实验题目 2
二、实验目的 2
三、实验要求 2
四、实现过程 3
1、实验设计： 3
2、调试分析： 8
3、运行结果： 9
4、实验总结： 9
五、参考文献 10

一、实验题目
蛮力法-串匹配问题
二、实验目的
(1)深刻理解并掌握蛮力法的设计思想；
(2)提高应用蛮力法设计算法的技能；
(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。
三、实验要求
1.[问题描述]：
给定两个字符串S和T，在主串S中查找子串T的过程称为串匹配，T称为模式。
设主串S=“abcabcacb”,模式=“abcac”。
2.[算法]：
蛮力法： 蛮力法（也称穷举法或枚举法）是一种简单直接的解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法，例如，对于给定的整数a和非负整数n，计算an的值，最直接最简单的方法就是把1和a相乘n次，即：an=a*a*a*···*a。
蛮力法所依赖的基本技术是遍历（也称扫描），即采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。依次处理所有元素是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。用蛮力法设计的算法，一般来说，都可以对算法的第一个版本进行一定程度的改进，提高其时间性能，但只能减少系数，而数量级不会改变。
四、实现过程
1、实验设计：
l 想法一：BF算法
1 在串S中和串T中设比较的下标i=1和j=1;
2 循环直到S中所剩字符个数小于T的长度或T中所有字符均比较完
2.1 k=i
2.2 如果S[i]=T[j],则比较S和T的下一字符,否则
2.2 将i和j回溯(i=k+1; j=1)
3 如果T中所有字符均比较完,则匹配成功,返回k，否则匹配失败,返回0
时间复杂度：设匹配成功发生在si处，则在i-1趟不成功的匹配中比较了（i-1）*m次，第i趟成功匹配共比较了m次，所以总共比较了i*m次，因此平均比较次数是：

一般情况下，m<<n,因此最坏情况下时间复杂度是Ο(n*m)。
l 想法二：KMP算法
实现过程：在串S和串T中高比较的起始下标i和j；循环直到S中所剩字符小于T的长度或T的所有字符均比较完（如果S[i]=T[j],则继续比较S和T的下一个字符；否则将j向右滑动到next[j]位置，即j=next[j];如果j=0,则将i和j分别+1，准备下趟比较，至于其中的next在此不作详细讲解）；如果T中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。 时间复杂度：当m<<n时，KMP算法的时间复杂性是Ο(n)。
l 图解过程

主串S 本趟匹配开始位置

si

模式T

tj

回溯

第一趟匹配，i=4，j=4失败，i回溯到1，j回溯到0
a
b
c
a
b
c
a
c
b
/0

0 1 2 3 4 5 6 7 8 9

a
b
c
a
c

第二趟匹配，i=1,j=0失败，i回溯到2，j回溯到0

a
b
c
a
b
c
a
c
b
/0
0 1 2 3 4 5 6 7 8 9

a

第三趟匹配，i=2,j=0,失败，i回溯到3，j回溯到0
0 1 2 3 4 5 6 7 8 9
A
b
c
a
b
c
a
c
b
/0

a

第四趟匹配，i=8，j=5，T中全部字符都比较完毕，匹配成功
A
b
c
a
b
c
a
c
b
/0

a
b
c
a
c

l 算法实现
1）BF
int BF(char S[],char T[],int index)
{
index=0;
int i=0,j=0;
while((S[i] != '\0') && (T[j] != '\0'))
{
if(S[i]==T[j])
{
i++;
j++;
}
else
{
index++;
i=index;
j=0;}
}
if(T[j]=='\0') return index+1;
else return 0;
}
2）KMP
void GetNext(char T[],int next[])
{
int i,j,len;
next[0]=-1;
for(j=1;T[j]!='\0';j++)
{
for(len=j-1;len>=1;len--)
{
for(i=0;i<len;i++)
if(T[i] != T[j-len+i]) break;
if(i==len)
{
next[j]=len; break;
}
}
if(len<1) next[j]=0;
}
}

int KMP(char S[],char T[])
{
int i=0,j=0;
int next[80];
GetNext(T,next);
while(S[i] != '\0'&& T[j] != '\0')
{
if(S[i]==T[j])
{
i++;j++;
}
else
{
j=next[j];
if(j==-1)
{
i++;j++;
}
}
}
if(T[j]=='\0')
return (i-strlen(T)+1);
else return 0;
}
2、运行结果：

3、实验总结：
本次实验的学习进一步对蛮力法的理解，同时对数据结构的一些算法有更深的掌握，同时认识到自己对某些基础算法掌握的并不是很牢固，要加强自己的动手实践能力！
五、参考文献
[1] 王红梅 胡胡《算法设计与分析》 （第2版），北京：清华大学出版社，2013年
[2] 王红梅 等《数据结构（C++版）》 （第2版），北京：清华大学出版社，2011年

10