财经类 直播类网站开发,营销软文推广平台,个人网站需不需要搭建服务器,提升网站性能目录
1.简介
2.例题
2.1找出字符串第一个匹配项的下标
2.2最长公共前缀
2.3最长回文子串
2.4二进制求和
2.5字符串相乘 1.简介 关于字符串匹配的常用算法KMP#xff0c;我这里只做思路上的说明#xff0c;具体内容文字和图片写来写去还是有点怪异#xff0c;这边推荐…目录
1.简介
2.例题
2.1找出字符串第一个匹配项的下标
2.2最长公共前缀
2.3最长回文子串
2.4二进制求和
2.5字符串相乘 1.简介 关于字符串匹配的常用算法KMP我这里只做思路上的说明具体内容文字和图片写来写去还是有点怪异这边推荐视频KMP 学一遍忘一遍ACM 金牌选手用可视化直击本质理解了内核后想忘记都难_哔哩哔哩_bilibili 该视频虽然短但对kmp的核心前缀函数做了比较清晰的说明从如何利用前缀函数写kmp到如何求前缀函数。思路脉络是比较清晰的。 现在我说下kmp的思路。 首先要理解如何利用前缀函数实现kmp。我们会有个数组pi然后把子串拼上一个特殊符号用来隔绝避免查找错误再拼上主串形成查找串从查找串的下标0开始遍历查找串我们把下标0到下标i的字符串称为临时串。 我们的p[i]存的这个临时串的前缀和后缀最大的匹配长度。这时候如何利用就已经很清晰了我们只需要找到p[i]等于子串长度也就是说查找串第i个位置形成的临时串前缀此时就是子串和后缀跟子串相等的长度相等。这时候通过偏移量i-子串长度*2就是主串中中该子串的位置(注意之所以*2是因为查找串已经是子串加特殊符号主串而根据末-首1字符串长度我们可以推出末-长度首-1也就是说按理来说i-子串长度是查找串种后缀子串第一个字符的前一个注意多了一个特殊字符所以-1可以不用了而为什么*2呢因为子串也加在查找串前面。) 说完怎么利用前缀函数实现kmp。 接下来我们讲怎么求前缀函数。设查找串a 假如我们要从p[x],那么假设p[0]----p[x-1]都可以求过了。 这时候我们先假设lenp[x-1]。如果a[len]a[x],说明a[x]正是a[0]---a[len-1]这个前缀的下一个。 但如果不等于呢那么我们要找第二长的len。一直往下直到len0了。 怎么找第二长或者说下一个长度呢首先从a[x-1]往前一定长度的子串a[len-1]往前的一定长度的子串。而又由于p[len-1]正好存的就是a[0]---a[len-1]的最大前后缀匹配长度 也就是说a[0]----a[0p[len-1]]正好等于a[x-1-p[len-1]]-----a[x-1]lenp[len-1],这时候重复最开始操作判断a[x]是否等于a[len]。如果这样也没有结果说明a[0]----a[x]并没有匹配的前后缀。也就是说p[x]0即可。 2.例题 2.1找出字符串第一个匹配项的下标 28. 找出字符串中第一个匹配项的下标 - 力扣LeetCode class Solution {
public:int pi[100000];int strStr(string haystack, string needle) {string searchneedle#haystack;//拼接子串、特殊符号、主串形成查找串int nhaystack.size(),mneedle.size();int xnm1;pi[0]0;for(int i1;ix;i)//遍历查找串{int lenpi[i-1];//假定len是0-i-1的临时串的最大前后缀匹配长度while(len!0search[i]!search[len])//如果i的字符跟len的字符不相等继续找下一个长度的pi{lenpi[len-1];//详细解释看上面}if(search[i]search[len])//详细解释看上面{pi[i]len1;if(pi[i]m){return i-m*2;}}}return -1;}
}; 2.2最长公共前缀 14. 最长公共前缀 - 力扣LeetCode 第一种思路把每一个字符串的每一个进行比较即可 class Solution {
public:string longestCommonPrefix(vectorstring strs) {string ans;int nstrs.size();int mstrs[0].size();int index0;while(indexm){int flag0;for(int i0;in-1;i){if(strs[i][index]!strs[i1][index]){flag1;break;}}if(flag)break;else ansstrs[0][index];}return ans;}
};class Solution {
public:string longestCommonPrefix(vectorstring strs) {int nstrs[0].size();int mstrs.size();for(int i0;in;i){for(int j1;jm;j){if(istrs[j].size()||strs[0][i]!strs[j][i]){return strs[0].substr(0,i);}}}return strs[0];}
}; 第二种思路两两比较比较费时写起来也比较繁琐。 class Solution {
public:string longestCommonPrefix(vectorstring strs) {string ansstrs[0];int nstrs.size();int mstrs[0].size();int index0;for(int i1;in;i){index0;int n1strs[i].size(),n2ans.size();while(indexn1indexn2){if(strs[i][index]ans[index]){index;}else{break;}}ansans.substr(0,index);}return ans;}
}; 2.3最长回文子串 5. 最长回文子串 - 力扣LeetCode 思路两种O(N2),O(n3),n3的我就不写了暴力枚举即可 这里写的是n2的思路 我们以每一位开始向左向右开始扩展。利用左右指针直到越界或不相等。 要注意奇数和偶数的可能性具体是指当前的位置可能是一个偶数长度回文串的偶数位置也可能正好是一个奇数长度回文串的中心位置。如1221,当前是第一个2。又比如12321当前是3 class Solution {
public:string longestPalindrome(string s) {int ns.size();string ans;for(int i0;in;i){int lefti,righti;while(left0rightns[left]s[right]){left--;right;}left,right--;if(right-left1ans.size()){anss.substr(left,right-left1);}lefti,righti1;if(i1n)continue;while(left0rightns[left]s[right]){left--;right;}if(leftirighti1)continue;left,right--;if(right-left1ans.size()){anss.substr(left,right-left1);}}return ans;}
}; 还可以再精简一下 class Solution {
public:string longestPalindrome(string s) {int ns.size();int al0,ar0;for(int i0;in;i){int lefti,righti;while(left0rightns[left]s[right]){left--;right;}left,right--;if(right-left1ar-al1){alleft,arright;}lefti,righti1;while(left0rightns[left]s[right]){left--;right;}left,right--;if(right-left1ar-al1){alleft,arright;}}return s.substr(al,ar-al1);}
}; 2.4二进制求和 67. 二进制求和 - 力扣LeetCode 高精度加法 -二进制 class Solution {
public:string addBinary(string a, string b) {int jw0;int naa.size(),nbb.size();int indexana-1,indexbnb-1;string ans;while(indexa0||indexb0||jw){int x0;if(indexa0)x(a[indexa--]-0);if(indexb0)x(b[indexb--]-0);if(jw)x,jw--;if(x2)jw,x-2;ans(x0);}reverse(ans.begin(),ans.end());return ans;}
}; 2.5字符串相乘 43. 字符串相乘 - 力扣LeetCode 思路1进制在中间就进行处理代码看着会比较费劲,其他就是用字符串模拟乘法 class Solution {
public:string addStrings(string a, string b) {if(a)return b;if(b)return a;int jw0;int naa.size(),nbb.size();int indexa0,indexb0;string ans;while(indexana||indexbnb||jw){int x0;if(indexana)x(a[indexa]-0);if(indexbnb)x(b[indexb]-0);if(jw)x,jw--;if(x10)jw,x-10;ans(x0);}return ans;}string multiply(string num1, string num2) {string res, ans;if(num1[0]0 || num2[0]0){return 0;}int n2 num2.size() - 1;int count 0;while (n2 0){int n1 num1.size() - 1;res.clear();int nu2 num2[n2] - 48;int j 0;while (n1 0||j){int sum0;int nu10;if(n10)nu1 num1[n1] - 48;if(n10)sum nu1 * nu2;if(j)sumj,j0;if(sum10)jsum/10,sumsum%10;res(sum0);if(n10)n1--;}n2--;string tmp;for (int i 0; i count; i){tmp 0;}tmpres;ansaddStrings(ans, tmp);count;}reverse(ans.begin(),ans.end());return ans;}
}; 思路2进制最后处理用数组模拟。 class Solution {
public:string multiply(string num1, string num2) {if(num10||num20)return 0;int n1num1.size(),n2num2.size();vectorintmp(n1n2,0);int zi0;for(int in1-1;i0;i--){for(int jn2-1;j0;j--){int index(n1-1-i)(n2-1-j);zimax(zi,index);int x(num1[i]-0)*(num2[j]-0);mp[index]x;}}int jw0;string ans;for(int i0;izi;i){if(jw)mp[i]jw,jw0;jwmp[i]/10;mp[i]mp[i]%10;ans(mp[i]0);}zi;while(jw){mp[zi]jw;jwmp[zi]/10;mp[zi]mp[zi]%10;ans(mp[zi]0);zi;}reverse(ans.begin(),ans.end());return ans;}
};
