3.2 顺序查找和蛮力字符串匹配

顺序查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstring>
using namespace std;

int SequentialSearch(string& a,char b)
{
	int i=0;
	while(i<a.length()&&a[i++]!=b);
	if(a[i-1]==b)i--;
	if(i<a.length())return i;
	else return -1;
}

int main()
{
	string a="abbbbc";
	cout<<SequentialSearch(a,'d')<<endl;
	cin.get();
	return 0;
}

蛮力字符串匹配：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstring>
using namespace std;

int BruteForceStringMatch(string& a,string& b,int n,int m)
{
	for(int i=0;i<=n-m;i++)
	{
		int j=0;
		while(j<m && b[j]==a[i+j])
		{
			j++;
			if(j==m)return i; 
		}
	}
	return -1;
}

int main()
{
	string a,b;
	a="aabbbd";
	b="d";
	cout<<a.length()<<' '<<b.length()<<endl;
	cout<<"字符串匹配的起始位置为 "<<BruteForceStringMatch(a,b,a.length(),b.length())<<endl; 
	cin.get();
	return 0;
}