字符串专题-1

目录

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]都可以求过了。

这时候，我们先假设len=p[x-1]。如果a[len]==a[x],说明a[x]正是a[0]---a[len-1]这个前缀的下一个。

但如果不等于呢，那么我们要找第二长的len。一直往下，直到len==0了。

怎么找第二长，或者说下一个长度呢？首先，从a[x-1]往前一定长度的子串==a[len-1]往前的一定长度的子串。而又由于，p[len-1]正好存的就是a[0]---a[len-1]的最大前后缀匹配长度，

也就是说，a[0]----a[0+p[len-1]]正好等于a[x-1-p[len-1]]-----a[x-1]，len=p[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 search=needle+'#'+haystack;//拼接子串、特殊符号、主串形成查找串int n=haystack.size(),m=needle.size();int x=n+m+1;pi[0]=0;for(int i=1;i<x;i++)//遍历查找串{int len=pi[i-1];//假定len是0-（i-1）的临时串的最大前后缀匹配长度while(len!=0&&search[i]!=search[len])//如果i的字符跟len的字符不相等，继续找下一个长度的pi{len=pi[len-1];//详细解释看上面}if(search[i]==search[len])//详细解释看上面{pi[i]=len+1;if(pi[i]==m){return i-m*2;}}}return -1;}
};

2.2最长公共前缀

14. 最长公共前缀 - 力扣（LeetCode）

第一种思路，把每一个字符串的每一个进行比较即可

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string ans="";int n=strs.size();int m=strs[0].size();int index=0;while(index<m){int flag=0;for(int i=0;i<n-1;i++){if(strs[i][index]!=strs[i+1][index]){flag=1;break;}}if(flag)break;else ans+=strs[0][index++];}return ans;}
};class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int n=strs[0].size();int m=strs.size();for(int i=0;i<n;i++){for(int j=1;j<m;j++){if(i==strs[j].size()||strs[0][i]!=strs[j][i]){return strs[0].substr(0,i);}}}return strs[0];}
};

第二种思路，两两比较，比较费时，写起来也比较繁琐。
 

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string ans=strs[0];int n=strs.size();int m=strs[0].size();int index=0;for(int i=1;i<n;i++){index=0;int n1=strs[i].size(),n2=ans.size();while(index<n1&&index<n2){if(strs[i][index]==ans[index]){index++;}else{break;}}ans=ans.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 n=s.size();string ans="";for(int i=0;i<n;i++){int left=i,right=i;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}left++,right--;if(right-left+1>ans.size()){ans=s.substr(left,right-left+1);}left=i,right=i+1;if(i+1>=n)continue;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}if(left==i&&right==i+1)continue;left++,right--;if(right-left+1>ans.size()){ans=s.substr(left,right-left+1);}}return ans;}
};

还可以再精简一下

class Solution {
public:string longestPalindrome(string s) {int n=s.size();int al=0,ar=0;for(int i=0;i<n;i++){int left=i,right=i;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}left++,right--;if(right-left+1>ar-al+1){al=left,ar=right;}left=i,right=i+1;while(left>=0&&right<n&&s[left]==s[right]){left--;right++;}left++,right--;if(right-left+1>ar-al+1){al=left,ar=right;}}return s.substr(al,ar-al+1);}
};

2.4二进制求和

67. 二进制求和 - 力扣（LeetCode）

高精度加法 -二进制

class Solution {
public:string addBinary(string a, string b) {int jw=0;int na=a.size(),nb=b.size();int indexa=na-1,indexb=nb-1;string ans="";while(indexa>=0||indexb>=0||jw){int x=0;if(indexa>=0)x+=(a[indexa--]-'0');if(indexb>=0)x+=(b[indexb--]-'0');if(jw)x++,jw--;if(x>=2)jw++,x-=2;ans+=(x+'0');}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 jw=0;int na=a.size(),nb=b.size();int indexa=0,indexb=0;string ans="";while(indexa<na||indexb<nb||jw){int x=0;if(indexa<na)x+=(a[indexa++]-'0');if(indexb<nb)x+=(b[indexb++]-'0');if(jw)x++,jw--;if(x>=10)jw++,x-=10;ans+=(x+'0');}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 sum=0;int nu1=0;if(n1>=0)nu1 = num1[n1] - 48;if(n1>=0)sum = nu1 * nu2;if(j)sum+=j,j=0;if(sum>=10)j=sum/10,sum=sum%10;res+=(sum+'0');if(n1>=0)n1--;}n2--;string tmp="";for (int i = 0; i < count; i++){tmp += '0';}tmp+=res;ans=addStrings(ans, tmp);count++;}reverse(ans.begin(),ans.end());return ans;}
};

思路2，进制最后处理，用数组模拟。

class Solution {
public:string multiply(string num1, string num2) {if(num1=="0"||num2=="0")return "0";int n1=num1.size(),n2=num2.size();vector<int>mp(n1+n2,0);int zi=0;for(int i=n1-1;i>=0;i--){for(int j=n2-1;j>=0;j--){int index=(n1-1-i)+(n2-1-j);zi=max(zi,index);int x=(num1[i]-'0')*(num2[j]-'0');mp[index]+=x;}}int jw=0;string ans="";for(int i=0;i<=zi;i++){if(jw)mp[i]+=jw,jw=0;jw=mp[i]/10;mp[i]=mp[i]%10;ans+=(mp[i]+'0');}zi++;while(jw){mp[zi]+=jw;jw=mp[zi]/10;mp[zi]=mp[zi]%10;ans+=(mp[zi]+'0');zi++;}reverse(ans.begin(),ans.end());return ans;}
};