如何建微信商城网站,太突然我国突然宣布,怎么制作app软件教程,六年级上册如何做网站前言
KMP真厉害#xff0c;刷题刷到 28.找出字符串中第一个匹配项的下标 和 1668.最大重复子字符串
next 数组用来匹配不上时#xff0c;前缀 j j j 可以快速回退到 n e x t [ j − 1 ] next[j-1] next[j−1] 的位置。
void getNext(vectorint next, const…前言
KMP真厉害刷题刷到 28.找出字符串中第一个匹配项的下标 和 1668.最大重复子字符串
next 数组用来匹配不上时前缀 j j j 可以快速回退到 n e x t [ j − 1 ] next[j-1] next[j−1] 的位置。
void getNext(vectorint next, const string s) {int j 0; // 后缀// next[0] 0; // next初始化为 0for (int i 1; i s.size(); i) {while (j 0 s[i] ! s[j])j next[j-1]; // 往回跳if (s[i] s[j])j;next[i] j; // 更新next数组}
}题目
28 找出字符串中第一个匹配项的下标 模版题 getNext可以重复使用
class Solution {
public:void getNext(vectorint next, const string s) {int j 0; // 后缀// next[0] 0; // next初始化为 0for (int i 1; i s.size(); i) {while (j 0 s[i] ! s[j])j next[j-1]; // 往回跳if (s[i] s[j])j;next[i] j; // 更新next数组}}int strStr(string haystack, string needle) {// needle是子串if (haystack.size() 0 || needle.size() 0)return -1;vectorint next(needle.size(), 0);// 构建 next 数组getNext(next, needle);int j 0;for (int i 0; i haystack.size(); i) {while (j 0 haystack[i] ! needle[j])j next[j-1];if (haystack[i] needle[j])j;if (j needle.size())return i - j 1;}return -1;}
};1668 最大重复子字符串 KMP 动态规划很难想象这是 简单 题
class Solution {
public:void getNext(vectorint next, string s) {int j 0; // 后缀for (int i 1; i s.size(); i) {while (j 0 s[i] ! s[j])j next[j - 1]; // 回退if (s[i] s[j])j;next[i] j;}}int maxRepeating(string sequence, string word) {int n sequence.size(), m word.size();if (n m)return 0;vectorint next(m, 0);getNext(next, word);// 动态规划 dp[i]表示 sequence[0..i]最多有dp[i]个wordvectorint dp(n, 0); int j 0;for (int i 0; i sequence.size(); i) {while(j 0 sequence[i] ! word[j])j next[j - 1];if (sequence[i] word[j])j;if (j m) { // 匹配上了开始 dp 操作if (i m)dp[i] dp[i - m] 1;elsedp[i] 1;}}int maxVal 0;for (int val: dp)maxVal max(maxVal, val);return maxVal;}
};
