串
Created At :
模式匹配算法
BF(暴力)
* 遍历所有的字符串可能性,然后与模式串进行比较.
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.size();
int n = needle.size();
if(n==0) return 0;
for(int i = 0; i <= m-n; ++i)
{
int j;
for(j = 0; j < n; ++j)
{
if(haystack[i+j] != needle[j])
break;
}
if(j == n) return i;
}
return -1;
}
};
- 时间复杂度:O(MN)
- 最坏情况:每次与模式串最后一个关键字不同,导致遍历了所有字符串可能性.
- 空间复杂地:O(1)
KMP
- KMP的关键点
- 求next数组
- next[i]表示匹配串中前i个字符中前缀和后缀字符相同的最大个数.
- 普通的next数组的方法为n^2
- 利用next[i-1]的值可以递推出next[i]的值
- 如果next[i-1] = k,则子串中前k个字符和后k个字符相同,只需比较s[k]和s[i]的大小
- 如果 s[k] == s[i],则next[i] = next[i-1]+1;
- 如果 s[k] != s[i],这时候需要看前缀的不匹配位置前的子串,通过将s[next[k-1]]和s[i]比较.不断重复该操作直到为0或者达到匹配.
- 这一步相当于拿needle的前缀去匹配后缀,得到前缀和后缀中的最大子前缀和后缀相同的大小.(具体可以看王道)
- 匹配过程和求next数组类似
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.size();
int n = needle.size();
if(n==0) return 0;
// 生成next数组
// 该next数组为非优化的,next[i]表示前i个字符的最大前后缀个数
vector<int> next(n,0);
next[0] = 0;
int j = 0;
for(int i = 1; i < n; ++i)
{
while(j > 0 && needle[i] != needle[j])
{
//这一步相当于拿needle的前缀去匹配后缀,得到前缀和后缀中的最大子前缀和后缀相同的大小.
j = next[j-1];
}
if(needle[i] == needle[j])
++j;
next[i] = j;
}
j = 0;
for(int i = 0; i < m; ++i)
{
while(j > 0 && haystack[i] != needle[j])
j = next[j-1];
if(haystack[i] == needle[j])
++j;
if(j == n)
return i - n+1;
}
return -1;
return 0;
}
};
BM
RK
Sunday