主要利用C++中的查找api find()
或者手写复现KMP算法来进行更高效的匹配
当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
- 两个字符串进行匹配，定义主串(query)和模式串(pattern)， 确定主串是否包含模式串
- 如何减少暴力搜索的匹配次数是KMP要解决的问题：
- 通过调整模式串的移动方式来避免重复的移动
- KMP算法的关键就在于如何设计模式串的移动/匹配规则
https://leetcode-cn.com/problems/implement-strstr/solution/kmp-suan-fa-xiang-jie-by-labuladong/
- 基于有限状态机进行理解：pat：
ABABC当匹配到不同的主串字符时的移动情况，可以用下面的状态转移图表示
- 那么如果构建这样的状态图呢？关键在于当前状态如何回退，正常情况下往下遍历很简单，但是当出现不匹配时如何进行有效的回退，也就是状态转移图中的返回。
- 基于标准代码进行分析：
- 暴力法中的回退法则就是遇到不相等的字符就从模式串头部开始遍历，也就是所有字符都是
next[i] = 0 - 这里用next[i] 表示如果出现模式串
p[i]!=T[j]时，下一个回退的位置 - 基本情况：
- 当在模式串第一个字符就不等时， 这时模式串无法回退，应该是主串指针后移， 设置特殊状态：
next[0] = -1表示主串后移
- 当在模式串第一个字符就不等时， 这时模式串无法回退，应该是主串指针后移， 设置特殊状态：
- 那么更通用的情况下：当前位置的前一位置[i-1]的回退位置为k，如果模式串p[k+1]==p[j], 那么当前回退位置就是k + 1，即
next[i] = k + 1 - 若模式串
p[k+1]!=p[j],那么这里就要往前回退，k = next[k]，寻找最优的前缀 - 整个过程是在寻找最长前后缀长度，但利用上面的分析过程会更容易理解整个实现过程
- 暴力法中的回退法则就是遇到不相等的字符就从模式串头部开始遍历，也就是所有字符都是
vector<int> getNext(string ps) {
vector<int> next(ps.size(), -1);
for (int i = 1; i < ps.size(); i++) {
int k = next[i - 1];
while (k != -1 && ps[k + 1] != ps[i]) {
k = next[k];
}
if (ps[k + 1] == ps[i]) {
next[i] = k + 1;
}
}
return next;
}前缀表： next数组 用于记录回退位置，记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配- 记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀 （最长相等前后缀/最长公共前后缀）模式串aabaaf
- **
前缀**是指不包含最后一个字符的所有以第一个字符开头的连续子串。a aa aab aaba aabaa
- **
后缀**是指不包含第一个字符的所有以最后一个字符结尾的连续子串abaaf baaf aaf af f
- 如下图，前五个元素构成的子串的最长公共前后缀长度为2
- 前缀表的使用： 找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。
- 为什么要前一个字符的前缀表的数值？
- 因为要找前面字符串的最长相同的前缀和后缀，所以要看前一位的前缀表的数值。
- 代码中
query[i] != pattern[j+1] => j = next[j]
- 前缀表计算；next
vector<int> getNext(string ps) {
vector<int> next(ps.size(), -1); // 初始化首字符回退-1 设为0也可
for (int i = 1; i < ps.size(); i++) {// 从1开始 即第二个开始搜索；
int k = next[i - 1]; // k来表示后缀串的开端
while (k != -1 && ps[k + 1] != ps[i]) { // 当前后缀不等时，进行回退
k = next[k];
}
if (ps[k + 1] == ps[i]) {// 找到相同的前后缀，进行记录
next[i] = k + 1;
}
}
return next;
}- 完整KMP代码如下： 建议全文背诵
- 匹配过程与取next过程基本一致，按照相同逻辑进行模式串回退即可
- 时间复杂度O(N) 空间复杂度O(N)
class Solution {
public:
vector<int> getNext(string pat) {
vector<int> next(pat.size(), -1);
for (int i = 1; i < pat.size(); i++) {
int k = next[i - 1];
while (k != -1 && pat[k + 1] != pat[i])
k = next[k];
if (pat[k + 1] == pat[i]) {
next[i] = k + 1;
}
}
return next;
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) return 0;
int n = haystack.size();
int m = needle.size();
vector<int> next = getNext(needle);
int j = -1;
for (int i = 0; i < n; i++) {
while (j != -1 && needle[j + 1] != haystack[i]) {
j = next[j];
}
if (needle[j + 1] == haystack[i]) {
j++;
if (j == m - 1)
return (i - m + 1);
}
}
return -1;
}
};- KMP查找算法，定义最大相同前后缀长度，计算子串各位置的最大前缀长度，当出现不匹配时根据最大前缀长度进行回退 时间复杂度(O(N))
- 常见面试题，需要深入了解并记住该原理，可以动态规划求解：前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
- 字符串匹配算法：还有Sunday 匹配机制相对比较简单：
class Solution {
public:
void get_next(vector<int> &next,string &s){
int j=-1;
next[0]=j;
for(int i=1;i<s.length();i++){
//回溯
while(j>=0&&s[j+1]!=s[i])
{
j=next[j];
}
if(s[j+1]==s[i]){
j++;
}
next[i]=j;
}
}
int strStr(string haystack, string needle) {
if(needle.length()==0) return 0;
vector<int> next(needle.length());
get_next(next,needle);
int j=-1;
for(int i=0; i<haystack.length();i++){
int ns=0;
while(j>=0&&haystack[i]!=needle[j+1]){
j=next[j];
}
if(haystack[i]==needle[j+1]){
j++;
}
if(j==needle.size()-1)
return (i-needle.size()+1);
}
return -1;
}
};- 更简单的匹配方法：记录待匹配子串的位移表，即每一个在子串 中出现的字符，在子串中出现的最右位置到尾部的距离+1，即记录在匹配失败后的最小移动长度
- 在匹配失败后根据位移表，调整目标串的遍历指针位置，如果下个字符出现在子串中，根据位移表进行指针移动；否则直接将位置移动len+1个位置。
- 时间复杂度O(n)，最差情况：O(mn)
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.length()==0) return 0;
unordered_map<int,int> shift;
int len=needle.length();
for(int i=len-1;i>=0;i--){
if(shift.count(needle[i]))
continue;
shift[needle[i]]=len-i;
}
int ns=0;
int start=0;
int i=start;
while( i<haystack.length()){
if(haystack[i]!=needle[ns]){
if(start+len<haystack.length()){
if(shift.count(haystack[start+len])){
start=start+shift[haystack[start+len]];
}else{
start=start+len+1;
}
i=start;
}
else{
return -1;
}
ns=0;
}
else{
ns++;
i++;
if(ns==needle.length()){
return start;
}
}
}
return -1;
}
};
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成 输入: "abab" 输出: True
- 可以将问题转换为字符串匹配问题：
- 对于目标串s，拼接得到 s+s,从第2个字符开始搜索，如果还能搜索出s，说明s内部是有循环节的
- 关键点 ：
掌握KMP算法每天看一遍 - 调用API实现
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s).find(s, 1) != s.size() ;
}
};- 手动KMP算法实现：
- KMP查找算法，定义最大相同前后缀长度，计算子串各位置的最大前缀长度，当出现不匹配时根据最大前缀长度进行回退
- 注意搜索范围： 是[1,2n-1]
- 时间复杂度(O(N))
- 代码结构：
- 构造next数组函数
- KMP搜索
- https://www.jianshu.com/p/dcfa55a773f0
- https://www.cnblogs.com/yjiyjige/p/3263858.html
class Solution {
public:
// 构造next数组
vector<int> getNext(string ps) {
vector<int> next(ps.size(), -1);
for (int i = 1; i < ps.size(); i++) {
int k = next[i - 1];
while (k != -1 && ps[k + 1] != ps[i]) {
k = next[k];
}
if (ps[k + 1] == ps[i]) {
next[i] = k + 1;
}
}
return next;
}
bool kmp(string query, string pattern, int beg) {
int n = query.size();
int m = pattern.size();
vector<int> next = getNext(pattern);
int k = -1;
// 搜索空间 [1, 2n-1]
for (int i = beg; i < n - 1; i++) {
while (k != -1 && pattern[k + 1] != query[i]) {
k = next[k];
}
if (pattern[k + 1] == query[i]) {
k++;
if (k == m - 1)
return true;
}
}
return false;
}
bool repeatedSubstringPattern(string s) {
return kmp((s + s), s, 1);
}
};给定两个字符串, A 和 B。A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde'，在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后，A 能变成B，那么返回True。
- 与[LC459题目]相似,在暴力法之外，需要考虑字符串匹配问题
- 将问题转换为 A + A串中是否包含 B 串
- 跟上题目一样可以使用KMP匹配算法来完成：时间复杂度 O(N) 空间复杂度 O(N)
- 优质KMP思路介绍
class Solution {
public:
vector<int> getNext(string B) {
vector<int> next(B.size(), -1);
for (int i = 1; i < B.size(); i++) {
int k = next[i - 1];
while (k != -1 && B[k + 1] != B[i]) {
k = next[k];
}
if (B[k + 1] == B[i]) {
next[i] = k + 1;
}
}
return next;
}
bool kmp(string A, string B, int beg) {
int n = A.size();
int m = B.size();
vector<int> next = getNext(B);
int k = -1;
for (int i = beg; i < n; i++) {
while (k != -1 && B[k + 1] != A[i]) {
k = next[k];
}
if (B[k + 1] == A[i]) {
k++;
if (k == m - 1)
return true;
}
}
return false;
}
bool rotateString(string A, string B) {
if (A == B) return true;
return A.size() == B.size() && kmp(A + A, B, 0);
//return A.size() == B.size() && (A + A).find(B) < A.size();
}
};给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。
- 多个字符串交叉匹配的问题；
- 使用双指针无法解决，存在局部非最优的情况
- 实际上还是要靠dp大法解决：
- 状态定义：
dp[i][j]表示s1前i个元素和s2前j个元素可以交错地构成s3的前i+j个元素 - 状态转移：
dp[i][j] = (dp[i-1][j] && s3[i+j-1]==s1[i-1]) | (dp[i][j-1] && s3[i+j-1]==s2[j-1]) - 一点细节： 定义为
[n+1][m+1]在遍历中也要考虑判断i>0/j>0
- 状态定义：
class Solution {
public:
// 初步尝试了双指针方法， 但双指针无法覆盖所有情况， 不是本题的解
bool isInterleave(string s1, string s2, string s3) {
int n = s1.size();
int m = s2.size();
int k = s3.size();
if (n + m != k) return false;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
dp[0][0] = 1;
// 考虑空字符串的情况： dp[i][j]: 第i个元素 第j个元素构成
// 设置[n+1][m+1]
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i > 0) {
dp[i][j] |= dp[i - 1][j] && (s3[i+j-1] == s1[i-1]);
}
if (j > 0) {
dp[i][j] |= dp[i][j-1] && (s3[i+j-1] == s2[j-1]);
}
}
}
return dp[n][m];
}
};- 空间压缩: 滚动数组
- 使用一维数组，注意避免覆盖
class Solution {
public:
// 初步尝试了双指针方法， 但双指针无法覆盖所有情况， 不是本题的解
bool isInterleave(string s1, string s2, string s3) {
int n = s1.size();
int m = s2.size();
int k = s3.size();
if (n + m != k) return false;
//vector<vector<int>> dp(n + 1, vector<int>(m + 1));
vector<int> dp(m + 1);
dp[0] = 1;
// 考虑空字符串的情况： dp[i][j]: 第i个元素 第j个元素构成
// 设置[n+1][m+1]
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i > 0) {
// dp[i][j] |= dp[i-1][j] && () 存在覆盖问题 需要避免dp[i-1][j]直接代替dp[i][j] 所以使用了&
dp[j] &= dp[j] && (s3[i+j-1] == s1[i-1]);
}
if (j > 0) {
dp[j] |= dp[j-1] && (s3[i+j-1] == s2[j-1]);
}
}
}
return dp[m];
}
};给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。 '.' 匹配任意单个字符 '' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次
- 注意
*的作用： 匹配前一个元素n次 （n>=0） - 那么根据这个特点，可以分为三种匹配情况：对于当前位置为
*:- 通配符匹配s串一个字符
dp[i][j-1] - 匹配s串0个字符
dp[i][j-2]当p串的前一个字符和当前s串的字符不匹配时，需要把前一个字符给忽略掉，即匹配0次 - 匹配s串多个字符
dp[i-1][j]
- 通配符匹配s串一个字符
class Solution {
public:
bool isMatch(string s, string p) {
s = " " + s; // 有效避免空字符串的对比问题
p = " " + p; // 防止 c* 或者 /n 的情况
int m = s.size();
int n = p.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[0][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 注意索引-1的情况 dp和实际string的索引有差
// 单个字符匹配
if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
else if (p[j - 1] == '*') {
// 考察p串前一个字符 无法匹配的情况下，*匹配0次
if (p[j - 2] != s[i - 1] && p[j - 2] != '.') {
dp[i][j] = dp[i][j - 2];
}
// 多次匹配
else { // p[j-2] == s[i-1] or p[j-2] == '.'
// dp[i][j-2] : 无法匹配
// dp[i][j-1] : 匹配1个
// dp[i-1][j] : 匹配多个a （s串）
dp[i][j] = dp[i][j - 2] || dp[i - 1][j] || dp[i][j - 1];
}
}
}
}
return dp[m][n];
}
};给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '' 的通配符匹配。 '?' 可以匹配任何单个字符。 '' 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
- 与[LC10.正则表达式]一题相似，但在具体的匹配规则上有差异：
- 本题，使用
*可以匹配任意字符串，匹配范围更广：
- 本题，使用
dp[i][j]表示s串的前i个字符和p串前j个字符匹配：s[i-1] == p[j-1] | p[j-1] == '?当前位置上字符匹配：dp[i][j] = dp[i-1][j-1]
- 如果当前位置上字符串不直接匹配的话，需要考虑
*的功效：dp[i][j] = dp[i-1][j] | dp[i][j-1]若p[j-1] == '*'- 即使用当前*进行匹配(
dp[i-1][j])与不使用*匹配(匹配空字符串dp[i][j-1])
- 即使用当前*进行匹配(
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size();
int m = p.size();
vector<vector<int>> dp(n + 1, vector<int> (m + 1));
// init 初始化设置 关键点
// 缺失部分设置将验证影响结果
dp[0][0] = 1;
for (int i = 1; i <= m; i++) {
if (p[i-1] == '*') {
dp[0][i] = dp[0][i-1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i-1] == p[j-1] || p[j-1] == '?') {
dp[i][j] = dp[i-1][j-1];
}
else if (p[j-1] == '*') {
dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i-1][j-1];
}
}
}
return dp[n][m];
}
};