wordpress媒体库没有东西,河北百度seo关键词排名,专业简历制作公司,如何查找昆明公司的网站给定一个字符串 s#xff0c;你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例 1#xff1a;
输入#xff1a;s aacecaaa
输出#xff1a;aaacecaaa示例 2#xff1a;
输入#xff1a;s 你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例 1
输入s aacecaaa
输出aaacecaaa示例 2
输入s abcd
输出dcbabcd提示
0 s.length 5 * 104s 仅由小写英文字母组成
解析
要找最短回文字符串我们可以想 设 s1 abab将其翻转 变成 s2 baba,合并字符串是为 s2 s1;
这时它并不是最短字符串s2s1 bababa可以进行合并。
相当于 abab
和 baba 进行kmp
在想想字符串前缀 和 后缀的关系我们可以想到KMP算法我们尽可能让前缀和后缀匹配的个数最多这时前缀个数后面的就是我们应该反转的。 class Solution {
public:string shortestPalindrome(string s) {int n s.size();vectorint fail (n,-1);for(int i 1;i n;i){int j fail[i-1];while(j ! -1s[j1] ! s[i]){j fail[j];}if(s[j 1] s[i]){fail[i] j1;}else fail[i] j;}int best -1;for(int i n - 1;i 0;i--){while(best ! -1 s[best1] ! s[i]){best fail[best];}if(s[best 1] s[i]){best;}}string add (best n-1 ? : s.substr(best1,n));reverse(add.begin(),add.end());return adds;}
};
时间复杂度为On;
这里还有一道题就是求给定一个长度为n的字符串问最短循环节问题。
用kmp做法
分析1.当字符串是由k个S1拼成的时候,next[n] k-1个s1长度所以最小循环节长度为n - next[n]
2. 当字符串为k个完整的s1和一个不完整的s1拼接的时候设s1长度为L不完整的为 Z next[n] (k-1)LZ, n - Next[n] kL Z - (k -1)L -Z L
综上所述最短长度为n - Next[n]
字符串哈希 可以用一个循环 class Solution {
public:string shortestPalindrome(string s) {int n s.size();int base 131, mod 1000000007;int left 0, right 0, mul 1;int best -1;for (int i 0; i n; i) {left ((long long)left * base s[i]) % mod;right (right (long long)mul * s[i]) % mod;if (left right) {best i;}mul (long long)mul * base % mod;}string add (best n - 1 ? : s.substr(best 1, n));reverse(add.begin(), add.end());return add s;}
}; O
