BF(Brute Force)算法是模式匹配中最简单最直观的算法, 其基本思想是从主串T(t0,t1,t2,t3…t(n-1))中的第start个自字符起和模式P的第一个字符进行比较, 如果相等, 则继续比较后续字符; 如果不相等, 则回溯至主串中的第start+1个字符位置继续和模式P进行比较. 以此类推, 直到模式P中每个字符都和主串T中的一个连续字符序列完全相同, 则匹配成功, 否则,匹配失败.
BF算法是一种蛮力算法, 其特点是简单直观, 但由于涉及到多次回溯, 算法效率很低. 不适用于信息量较大的情况.
下面给出BF的一个实现如下:
//
// main.cpp
// BF
//
// Created by Scarecrow on 16/12/7.
// Copyright © 2016年 XB. All rights reserved.
//
#include <iostream>
using namespace std;
#define NO_MATCH -1
#define LEN_ERROR -2
/**
字符串模式匹配之BF算法
@param t 主串
@param p 模式(子串)
@param start 起始匹配索引(t)
@return 匹配结果
*/
int bruteForce(char const t[], char const p[], int const start)
{
size_t len_t = strlen(t);
size_t len_p = strlen(p);
//如果要匹配的子串长度大于主串长度
if (len_t < len_p) {
return LEN_ERROR;
}
int index_t = start;
int index_p = 0;
while (index_p < len_p && index_t < len_t) {
if (t[index_t] == p[index_p]) {
++index_p;
++index_t;
}else{
index_t = index_t - index_p + 1;
index_p = 0;
}
}
if (index_p >= len_p) {
return index_t - index_p;
}
return NO_MATCH;
}
int main(int argc, const char * argv[]) {
char p[] = "fe";
char t[] = "feherrrfe";
int start = 3;
int index = bruteForce(t, p, start);
cout << index << endl;
return 0;
}