前言
本文将结合具体题目，进一步深化对于字符串算法的掌握运用。
C++算法
字符串算法进阶：公共前缀、回文子串与大数运算
介绍四种经典字符串算法题目。包括最长公共前缀的两两比较与统一比较解法；最长回文子串的中心拓展算法；二进制求和的模拟竖式计算；以及字符串乘法的大数模拟运算。通过 C++ 代码实现，解析核心思路与边界处理。
介绍四种经典字符串算法题目。包括最长公共前缀的两两比较与统一比较解法；最长回文子串的中心拓展算法；二进制求和的模拟竖式计算；以及字符串乘法的大数模拟运算。通过 C++ 代码实现，解析核心思路与边界处理。
本文将结合具体题目，进一步深化对于字符串算法的掌握运用。
现给出字符串数组，要求返回所有字符串的最长公共前缀。
解法一（两两比较）： 我们可以先找出前两个的最长公共前缀，然后拿这个最长公共前缀依次与后面的字符串比较，这样就可以找出所有字符串的最长公共前缀。
解法二（统一比较）： 题目要求多个字符串的公共前缀，我们可以逐位比较这些字符串，哪一位出现了不同，就在哪一位截止。
两两比较代码示例：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
// 解法一：两两比较
string ret = strs[0];
for(int i = 1; i < strs.size(); i++)
ret = findCommon(ret, strs[i]);
return ret;
}
string findCommon(string& s1, string& s2){
int i = 0;
while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
return s1.substr(0, i);
}
};
统一比较代码示例：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
// 所有字符串一起 逐个比较
string ret=strs[0];
for(int i=0;i<ret.size();i++){
char temp=strs[0][i];
for(int j=1;j<strs.size();j++){
if(i==strs[j].size()||temp!=strs[j][i]){
return ret.substr(0,i);
}
}
}
return ret;
}
};
题目要求找出字符串 s 中的最长回文子串，我们先来回顾一下什么是回文串。
回文串：即正反形式相同的字符串，例如 aba
本题我们可以采用中心拓展算法。
class Solution {
public:
string longestPalindrome(string s){
int n=s.size();
int left=0,right=0,len=0,begin=0;
for(int i=0;i<n;i++){
// 奇数次拓展
left=i,right=i;
while(left>=0&&right<n&&s[left]==s[right]){
left--; right++;
}
if(right-left-1>len){
begin=left+1; len=right-left-1;
}
// 偶数次拓展
left=i,right=i+1;
while(left>=0&&right<n&&s[left]==s[right]){
left--; right++;
}
if(right-left-1>len){
begin=left+1; len=right-left-1;
}
}
return s.substr(begin,len);
}
};
模拟十进制中我们列竖式计算两个数之和的过程。但是这里是二进制的求和，我们不是逢十进一，而是逢二进一。
class Solution {
public:
string addBinary(string a, string b){
int cur1=a.size()-1,cur2=b.size()-1;
string ret=""; // 返回的字符串
int t=0; // 进位
while(cur1>=0||cur2>=0||t){
if(cur1>=0){
t+=a[cur1--]-'0';
}
if(cur2>=0){
t+=b[cur2--]-'0';
}
ret+=t%2+'0';
t/=2;
}
reverse(ret.begin(),ret.end());
return ret;
}
};
整体思路就是模拟我们小学列竖式计算两个数相乘的过程。但是为了我们书写代码的方便性，我们选择一种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。
class Solution {
public:
string multiply(string num1, string num2){
int m=num1.size(),n=num2.size();
string ret="";
int len=m+n-1;
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
// 先逆序两个字符串
// 不进位的乘法
vector<int>temp(len);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
temp[i+j]+=(num1[i]-'0')*(num2[j]-'0'); // 此处注意是 +=
}
}
// 处理进位
int t=0,cur=0;
while(cur<len||t){
if(cur<len){
t+=temp[cur++];
}
ret+=t%10+'0';
t/=10;
}
// 处理前导 0
while(ret.size()>1&&ret.back()=='0'){
ret.pop_back();
}
reverse(ret.begin(),ret.end());
return ret;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online