一种暴力的串匹配算法。
指定主串中查找的起始位置。用两个指针分别遍历主串和子串,如果到达串尾就结束。 当遇到子串与主串不匹配时,通过把主串指针回溯到当前起始字符的下一个字符来重新开始匹配。
实现代码如下。
#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)
标签:主串,BF,ch,string,int,算法,length,SString,模式匹配 From: https://www.cnblogs.com/iszxh/p/17759451.html