给定一个字符串,你可以将它转换成一个回文通过添加字符在它前面。找到并返回最短的回文可以发现通过执行这个转换。　　　　例如: 　　　　鉴于“aacecaaa”,返回“aaacecaaa”。　　　　鉴于“abcd”,返回“dcbabcd”。-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.



For example:



Given　aacecaaa , return　aaacecaaa .



Given　abcd , return　dcbabcd .