LeetCode-214. Shortest Palindrome

LeetCode-214. Shortest Palindrome

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: ​​"aacecaaa"​​ Output: ​​"aaacecaaa"​​

Example 2:

Input: ​​"abcd"​​ Output: ​​"dcbabcd"​​

​​题解：​​

​​暴力肯定不是最优解。​​

​​本题考察的是KMP算法。​​

​​kmp算法：​​

题解：（还没怎么写过kmp，看讨论区写的，有时间再看看）

class Solution {public: string shortestPalindrome(string s) { int n = s.length(); string rs = s; reverse(rs.begin(), rs.end()); string l = s + '#' + rs; int ln = l.length(); vector next(ln, 0); for (int i = 1; i < ln; i++) { int j = next[i - 1]; while (j > 0 && l[i] != l[j]) { j = next[j - 1]; } if (l[i] == l[j]) { j++; } next[i] = j; } return rs.substr(0, n - next[ln - 1]) + s; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。