C++实现字符串匹配的暴力法

实验报告

??（系） ???班级 ?????学号?????????姓名???????

实验日期???年??月??日?????????????????????????????????????指导老师??????

实验名称 ???字符串匹配的蛮力实现???

实验目的 ??编写算法程序解决上述问题???

实验步骤（实验内容、写出代码和运行结果）

题目：

字符串算法主要可以分为几类。字符串匹配就是其中之一。当我们提到字符串匹配算法，最基本的方法就是所谓的蛮力解法,这意味着我们需要检查每一个文本串中的字符是否和匹配串相匹配。一般来说我们有文本串和一个匹配串(通常匹配串短于文本串)。我们需要做的就是回答这个匹配串是否出现在文本串中。要求用蛮力算法解决字符串的匹配问题。

代码实现：

#include<stdio.h>

#include <iostream>

using namespace std;

int i,j;

int a[100]={};

int m,n;

int p=0,k=1;

int f(string text,string pattern)

{

?????m = text.size();

?????n = pattern.size();

????

????for(i=0;i<=m-n;++i)

??{

?????????j=0;

????????while(j<n&&text[i+j]==pattern[j])

{

????????????j++;

????????}

????????

????????if(j==n)

{

????????????a[i]=1;

????????????p++;

????????}

??????}

????return 0;

}

int main(){

????string text;

????string pattern;

????cin>>text;

cin>>pattern;

????f(text,pattern);

????if(p==0)

????{

???? cout<<"不存在一致的字符串"<<endl;

}

????else

????{

???? cout<<"有"<<p<<"个一致的字符串，分别为："<<endl;

???? for(i=0;i<=m-n;i++)

???? {

???? if(a[i]==1)

???? {

???? ?cout<<"第"<<k<<"个一致字符串下标首位置是第"<<i+1<<"个字母"<<endl;

?k++;

}

????

}

????

}

????

????

????return 0;

}

运行结果：

实验总结体会（主要书写：上机过程碰到的问题，自己如何解决的，还有哪些疑问，对本次上机进行认真总结，自己的体会）

字符串匹配蛮力算法最关键一步就是要在小字符串判断完成后回到原来遍历位置的下一位，否则就会漏掉。总体来说，用蛮力法来解决字符串的匹配问题思路还是很清晰的，算法也不是很难，不过遇到数量级很大的文章和字符串的时候估计运算速度会很慢。