BF算法
BF算法流程
主串i和子串j分别从下标为0的地方开始匹配：
相等，向后移动：
相等，在向后移动：
此时就不相等了；
i和j分别回退：
继续比较：
不相等，继续向后移动。
一直退到这里：
相等，向后退：
还是相等的，继续退；
匹配成功：
当 j 和自己长度相等时，表示找到了
匹配失败：
移动到最后时：
此时不匹配，i会+1：
BF算法流程代码实现
#include <iostream>
#include <memory>
using namespace std;
// BF算法 时间复杂度：O(n)*O(m) = O(n*m) 空间复杂度： O(1)
int BF(string s, string t)
{
int i = 0;
int j = 0;
while (i < s.size() && j < t.size()) // O(n)
{
if (s[i] == t[j])
{
i++;
j++;
}
else
{
i = i - j + 1; // 复位i，指向之前开始匹配字符的下一个字符 O(m)
j = 0;
}
}
if (j == t.size()) // 找到了
{
return i - j;
}
else
{
return -1;
}
}
int main()
{
string s = "ABCDCABDEFG";
string t = "ABD";
int pos = BF(s, t);
cout << pos << endl;
}
BF算法的时间与空间复杂度
字符串优化算法： KMP、字典树、倒排索引
BF算法的问题
问题：
此时，不匹配，需要将i置为i-j+1，j=0;
然后，B和开头的A进行比较，其实是没有必要的，因为前面两个A，B本来就是不同的，相对应位相同，移动后，肯定不同啊。
#include <iostream>
#include <memory>
using namespace std;
// BF算法 时间复杂度：O(n)*O(m) = O(n*m) 空间复杂度： O(1)
int BF(string s, string t)
{
int i = 0;
int j = 0;
while (i < s.size() && j < t.size()) // O(n)
{
if (s[i] == t[j])
{
i++;
j++;
}
else
{
i = i - j + 1; // 复位i，指向之前开始匹配字符的下一个字符 O(m)
j = 0;
}
}
if (j == t.size()) // 找到了
{
return i - j;
}
else
{
return -1;
}
}
// KMP算法求解子串的next数组
int* getNext(string str)
{
int* next = new int[str.size()];
int j = 0; // j用来遍历子串
int k = -1; // k表示公共前后缀的长度
next[j] = k; //将第0个位置设置为-1
========================================未优化版本============================================
while (j < str.size() - 1) // O(m)
{
if (-1 == k || str[k] == str[j])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k]; //做k值的回溯，继续找最长的公共前缀
}
}
return next;
}
==============================================================================================
========================================优化版本===============================================
//注意: 优化后的next数组和未优化的next数组都是不一样的
while (j < str.size() - 1) // O(m)
//j < str.size() - 1取到倒数第2个字符，就可以求出最后一个字符前面的最后那个公共前后缀
{
if (-1 == k || str[k] == str[j])
{
j++;
k++;
if (str[k] == str[j])
{
// kmp算法的优化
next[j] = next[k];
}
else
{
next[j] = k;
}
}
else
{
k = next[k]; // 做k值回溯，继续找最长的公共前后缀
}
}
return next;
}
==============================================================================================
// KMP算法 时间复杂度：O(n) + O(m) = O(n+m) --O(n):KMP的while循环 --O(m):求next数组
// 空间复杂度：O(m)——next数组
int KMP(string s, string t)
{
int i = 0;
int j = 0;
// 计算一个子串对应的next数组
int* next = getNext(t);
unique_ptr<int> ptr(next); // delete操作
//打印next数组
cout << t << " : ";
for (int m = 0; m < t.size(); m++)
{
cout << next[m] << " ";
}
cout << endl;
// j < t.size() 有问题！！！ j = -1 11111111111 size_t unsigned int
int size1 = s.size();
int size2 = t.size();
while (i < size1 && j < size2) // O(n)
{
if (-1 == j || s[i] == t[j]) 如果首字母匹配失败，这里j == -1
{
i++;
j++;
}
else
{
// KMP的核心是不回退i，只回退j值
j = next[j]; // 如果首字母匹配失败，这里j == -1
//i = i - j + 1;
//j = 0;
}
}
if (j == t.size()) // 找到了
{
return i - j;
}
else
{
return -1;
}
}
int main()
{
string s = "abcabdefabcabc"; //"ABCDCABDEFG";
string t = "abcabc"; //"ABD";
int pos = KMP(s, t);
cout << pos << endl;
}
