字符串匹配——枚举法

给定主串T和模式串P，返回P在T中首次出现的位置，如果P不存在于T中，返回-1。

这样的问题就是字符串匹配问题，这里先给出枚举法的思想。

设主串T的长度为n,模式串P的长度为m。

主串从0到n-m，每次选取连续的m个字符，跟模式串P的m个字符进行一一比较。

伪代码

BruteForce(T, P)
01 for s <- 0 to n - m
02  j <- 0
03  // check if T[s...s+m-1] = p[0...m-1]
04  while T[s+j] = P[j] do
05      j <- j + 1
06      if j = m then return s;
07 return -1

实现代码

// 布鲁特逼近法也就是穷举法
int bruteForce(const string &T,const string &P) {// 主串的长度int n = T.length();// 模式串的长度int m = P.length();for(int i = 0; i <= n - m; i++) {// 比较串T[i...i+m-1]和P[0...m-1]for(int j = 0; j < m; j++) {// 匹配失败则T指向下一个元素// P从零开始if(T[i + j] != P[j]) {break;}// 在主串中找到模式串if(j == m - 1) {// 返回模式串在主串的最早出现位置return i;}}}// 未在主串中找到模式串return -1;
}

测试主程序

#include <iostream>
#include <string>using namespace std;// 布鲁特逼近法也就是穷举法
int bruteForce(const string &T,const string &P) {// 主串的长度int n = T.length();// 模式串的长度int m = P.length();for(int i = 0; i <= n - m; i++) {// 比较串T[i...i+m-1]和P[0...m-1]for(int j = 0; j < m; j++) {// 匹配失败则T指向下一个元素// P从零开始if(T[i + j] != P[j]) {break;}// 在主串中找到模式串if(j == m - 1) {// 返回模式串在主串的最早出现位置return i;}}}// 未在主串中找到模式串return -1;
}/**
IN
at the thought of
thoughOUT
7
**/
int main() {// 主串和模式串string T, P;while(true) {// 获取一行getline(cin, T);getline(cin, P);int res = bruteForce(T, P);if(res == -1) {cout << "主串和模式串不匹配。" << endl;} else {cout << "模式串在主串的位置为：" << res << endl;}}return 0;
}

算法分析

最坏情况

• 外层循环：n-m
• 内层循环：m
• 总计(n-m)m = O(nm)

最好情况

• n-m

完全随机的主串和模式串

• O(n - m)