数组和字符串-字符串

最长公共前缀

题意：

给多个字符串，找最长前缀

解：

暴力匹配，先按字典序排序字符串，这样长度短的优先进行匹配，所得字符串就可能偏小

适合a aa aaa aaaa这样的数据，不过对于aa aab aabc aabcd没用

代码：

#include<bits/stdc++.h>
using namespace std;
string solve(const string &s1,const string &s2)
{string ans;int lg=min(s1.size(),s2.size());for(int i=0;i<lg;i++){if(s1[i]==s2[i]) ans.push_back(s1[i]);else break;}return ans;
}
string longestCommonPrefix(vector<string>& strs)
{sort(strs.begin(),strs.end());int lg=strs.size();if(lg==1) return strs[0];string ans=solve(strs[0],strs[1]);for(int i=2;i<lg;i++){ans=solve(ans,strs[i]);if(ans.empty()) break;}return ans;
}
int main()
{vector<string>strs;string str;while(cin>>str){strs.push_back(str);}string ans=longestCommonPrefix(strs);cout<<ans<<endl;return 0;
}

最长回文子串

题意：

如题

解：

枚举每个子串的中间段，需要特别注意中间段的长度可以为奇数也可以为偶数

所以处理的时候，先把和给定中心点相邻的相同字符都归入中间段

代码：

#include<bits/stdc++.h>
using namespace std;
string longestPalindrome(string s)
{string ret;int ans=0,lg=s.size();for(int i=0;i<lg;i++){int l=i,r=i;while(r+1<lg&&s[r+1]==s[l]) r++;while(l-1>=0&&s[l-1]==s[r]) l--;while(r+1<lg && l-1>=0 &&s[r+1]==s[l-1]){l--;r++;}if(r-l+1>ans){ans=r-l+1;ret=s.substr(l,r-l+1);}}return ret;
}
int main()
{string s;cin>>s;string ans=longestPalindrome(s);cout<<ans<<endl;return 0;
}

翻转字符串里的单词

题意：

将单词顺序翻转，单词保持原样

解：

先整体翻转，然后轮流执行单词翻转和多个空格替换成一个空格

代码：

#include<bits/stdc++.h>
using namespace std;
string reverseWords(string s)
{int l=0,lg=s.size(),r=lg-1;while(s[l]==' ')l++;while(s[r]==' ')r--;s=s.substr(l,r-l+1);lg=s.size();reverse(s.begin(),s.end());bool zt=1;l=0,r=0;while(l<s.size()){while(zt&&r<s.size()&&s[r]!=' ')r++;if(zt==1&&l<s.size()){reverse(s.begin()+l,s.begin()+r);l=r;zt=0;}while(zt==0 &&r<s.size()&& s[r]==' ')r++;if(zt==0&&l<s.size()){s.replace(s.begin()+l,s.begin()+r," ");l++;r=l;zt=1;}}return s;
}
int main()
{string s;getline(cin,s);string ans=reverseWords(s);cout<<ans<<endl;return 0;
}

实现 strStr()

题意：

实现字符串匹配KMP算法

解：

KMP板子，next数组里存的是最长相同前后缀，next[length]表示[0,length-1]（不包含length）的最长相同前后缀，前后缀不能包含整个子串，就如[0,length-1]的前缀最多取到[0,length-2]，所以构建next的时候，mao=1,had=0

代码：

#include<bits/stdc++.h>
using namespace std;
void getNext(vector<int>&next,const string& needle)
{const int lg=needle.size();next.resize(lg+1);int mao=1,had=0;for(;mao<lg;mao++){while(had && needle[mao]!=needle[had]) had=next[had];if(needle[mao]==needle[had]) had++;next[mao+1]=had;}//for(auto n:next) cout<<n<<endl;
}
int strStr(string haystack, string needle)
{vector<int> next;getNext(next,needle);cout<<"getNext Done"<<endl;const int lg=haystack.size();int mao=0,had=0;for(;mao<lg;mao++){while(had && haystack[mao]!=needle[had]) had=next[had];if(haystack[mao]==needle[had]) had++;if(had==needle.size()) return mao-had+1;}return -1;
}
int main()
{string haystack,needle;cin>>haystack>>needle;int ans=strStr(haystack,needle);
}