php网站建设平台搭建,wordpress文章分享代码,苏州网站建设多少钱,公司简介ppt模板范文免费最长公共前缀
题意#xff1a;
给多个字符串#xff0c;找最长前缀
解#xff1a;
暴力匹配#xff0c;先按字典序排序字符串#xff0c;这样长度短的优先进行匹配#xff0c;所得字符串就可能偏小
适合a aa aaa aaaa这样的数据#xff0c;不过对于aa aab aabc aab…最长公共前缀
题意
给多个字符串找最长前缀
解
暴力匹配先按字典序排序字符串这样长度短的优先进行匹配所得字符串就可能偏小
适合a aa aaa aaaa这样的数据不过对于aa aab aabc aabcd没用
代码
#includebits/stdc.h
using namespace std;
string solve(const string s1,const string s2)
{string ans;int lgmin(s1.size(),s2.size());for(int i0;ilg;i){if(s1[i]s2[i]) ans.push_back(s1[i]);else break;}return ans;
}
string longestCommonPrefix(vectorstring strs)
{sort(strs.begin(),strs.end());int lgstrs.size();if(lg1) return strs[0];string anssolve(strs[0],strs[1]);for(int i2;ilg;i){anssolve(ans,strs[i]);if(ans.empty()) break;}return ans;
}
int main()
{vectorstringstrs;string str;while(cinstr){strs.push_back(str);}string anslongestCommonPrefix(strs);coutansendl;return 0;
}最长回文子串
题意
如题
解
枚举每个子串的中间段需要特别注意中间段的长度可以为奇数也可以为偶数
所以处理的时候先把和给定中心点相邻的相同字符都归入中间段
代码
#includebits/stdc.h
using namespace std;
string longestPalindrome(string s)
{string ret;int ans0,lgs.size();for(int i0;ilg;i){int li,ri;while(r1lgs[r1]s[l]) r;while(l-10s[l-1]s[r]) l--;while(r1lg l-10 s[r1]s[l-1]){l--;r;}if(r-l1ans){ansr-l1;rets.substr(l,r-l1);}}return ret;
}
int main()
{string s;cins;string anslongestPalindrome(s);coutansendl;return 0;
}翻转字符串里的单词
题意
将单词顺序翻转单词保持原样
解
先整体翻转然后轮流执行单词翻转和多个空格替换成一个空格
代码
#includebits/stdc.h
using namespace std;
string reverseWords(string s)
{int l0,lgs.size(),rlg-1;while(s[l] )l;while(s[r] )r--;ss.substr(l,r-l1);lgs.size();reverse(s.begin(),s.end());bool zt1;l0,r0;while(ls.size()){while(ztrs.size()s[r]! )r;if(zt1ls.size()){reverse(s.begin()l,s.begin()r);lr;zt0;}while(zt0 rs.size() s[r] )r;if(zt0ls.size()){s.replace(s.begin()l,s.begin()r, );l;rl;zt1;}}return s;
}
int main()
{string s;getline(cin,s);string ansreverseWords(s);coutansendl;return 0;
}实现 strStr()
题意
实现字符串匹配KMP算法
解
KMP板子next数组里存的是最长相同前后缀next[length]表示[0,length-1]不包含length的最长相同前后缀前后缀不能包含整个子串就如[0,length-1]的前缀最多取到[0,length-2]所以构建next的时候mao1,had0
代码
#includebits/stdc.h
using namespace std;
void getNext(vectorintnext,const string needle)
{const int lgneedle.size();next.resize(lg1);int mao1,had0;for(;maolg;mao){while(had needle[mao]!needle[had]) hadnext[had];if(needle[mao]needle[had]) had;next[mao1]had;}//for(auto n:next) coutnendl;
}
int strStr(string haystack, string needle)
{vectorint next;getNext(next,needle);coutgetNext Doneendl;const int lghaystack.size();int mao0,had0;for(;maolg;mao){while(had haystack[mao]!needle[had]) hadnext[had];if(haystack[mao]needle[had]) had;if(hadneedle.size()) return mao-had1;}return -1;
}
int main()
{string haystack,needle;cinhaystackneedle;int ansstrStr(haystack,needle);
}
