朴素模式匹配算法又称简单匹配算法或Brute-Force算法,它是字符串模式匹配中比较简单的一种算法。它从主串的第一个字符开始进行模式匹配,依次比较主串和模式串中的每个字符,若比较全部相等(模式匹配成功),则返回模式串中第一个字符在主串中的位置,否则主串指针从比较失败的字符处回溯到第二个字符开始重新和模式串进行匹配,这样依此下去,直到和模式串匹配成功或到主串的末尾(匹配不成功)为止。
朴素模式匹配算法的C/C++代码实现:
// 定义一个字符串结构体
typedef struct {
char data[MAX_SIZE];
int length;
} string;
int BruteForce(string s, string t)
{
int i = 0, j = 0;
while (i < s.length && j < t.length) {
if (s[i] == t[j]) {
i++;
j++;
} else {
i = i - j + 1; // 主串指针回溯
j = 0;
}
}
if (j > t.length)
return i - t.length;
else
return -1;
}