字符串匹配
子串匹配问题
子串匹配又叫模式串匹配
例如 ab 是 sdabc的子串，ab又称为模式串，sdabc又成为主串。
怎么样判断一个字符串是另一个字符串的子串，在文档中的查找、匹配等待都会用到。
BF
利用滑动窗口，一步一步与主串进行比较，不对，让主串后移一位，重新与模式串进行比较。直到模式串完全匹配
int bf(const string& patten, const string&str){
int i{0};
int j{0};
for(; i <= str.length()-patten.length();i++){
for(j=0; j < patten.length();j++){
if(patten[j]!=str[j+i])break;
}
if(j==patten.length())return i;
}
return -1;
}时间复杂度O(mn)
KMP
可以先看，维基百科中的介绍
这里代码实现主要难在next数组求解上，这里引用一下b站的一张图片，来解释next数组求解第二种情况，有时间可以看一下up的视频。
#include <iostream>
#include <vector>
using namespace std;
/*next 中数字的含义
* -1 当前与匹配字符串，不同，需要匹配的主串移动，再与模式串重新比
* other 让j回到 other 处，再与主串进行比对。
*
*/
vector<int> getNext(const string& pattern) {
vector<int> next;
//字符串多长，next数组就多长，
next.reserve(pattern.length());
//因为一个next肯定是-1，所以将j=-1，i=0
//i代表模式串中当前所要计算next的位置
//j代表最大的前缀尾
int j{-1},i{0};
next.push_back(-1);
/*
* 举例说明
* 当计算next[4]时，如果pattern[3]与next[3]的最大前后缀最后面的下一个字符相同，那么next[4] = next[3]+1
* 如果不相等，而next[i]含义就是找到以pattern[i-1]结尾的最大前后缀，所以比较pattern中 i与next[j]的值
* loop
*/
while(i<pattern.length()-1){
if(j==-1||pattern[i]==pattern[j]){
next.push_back(++j);
i++;
}else{
j = next[j];
}
}
return next;
}
//返回result
class result{
public:
bool res{false};
int index{-1};
result() = default;
};
result isSubstring(const string& pattern, const string& str){
result res;
if(pattern.length()>=str.length())return res;
int i{0};
int j{0};
vector<int> next = getNext(pattern);
while(i<str.length()){
if(str[i]==pattern[j]){
i++;
j++;
}else{
j = next[j];
if(j==-1){
j = 0;
i++;
continue;
}
}
if(j==pattern.length()){
res.res = true;
res.index = i-j;
break;
}
}
return res;
}
int main(){
string pattern = "abaabcaba";
string s = "bcabsd";
vector<int> ans = getNext(s);
for(int &a: ans){
cout<<a<<" ";
}
cout<<endl;
result res = isSubstring(s, pattern);
if(res.res){
cout<< res.index<<endl;
}
}