JZTXT

串模式匹配-BF算法

发布时间 2023-10-12 14:51:50作者: ww0809

一种暴力的串匹配算法。
指定主串中查找的起始位置。用两个指针分别遍历主串和子串，如果到达串尾就结束。 当遇到子串与主串不匹配时，通过把主串指针回溯到当前起始字符的下一个字符来重新开始匹配。

实现代码如下。

#include<iostream>
using namespace std;

#define MAXLEN 255

typedef struct {
    char ch[MAXLEN + 1]; // 谨防数组越界！！！之前某次写循环队列，
	//因为数组开的不够大，导致输入的字符串结束符没地方存，狂调一节课
    int length;
} SString;

void input_string(SString &s, SString &t) {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> s.ch[i];
    s.length = n;
    for(int i = 1; i <= m; i++) cin >> t.ch[i];
    t.length = m;
}

void out_string(SString s) {
    for(int i = 1; i <= s.length; i++) cout << s.ch[i] << " ";
    cout << endl;
} // 其实并没有用到这个函数

int index_bf(SString s, SString t, int pos) {
    int i = pos, j = 1;
    while(i <= s.length && j <= t.length) {
        if(s.ch[i] == t.ch[j]) i++, j++; // 如果匹配就比较下一位
        else i = i - j + 2, j = 1; // 如果不匹配 回溯主串指针 把子串指针拉到开头
    } 
    if(j > t.length) return i - t.length;
    else return 0;
}

int main() {
    SString s, t;
    input_string(s, t);
    cout << index_bf(s, t, 1);
    return 0;
}

时间复杂度：最好O(n + m) 最坏O(m * n)