给定一个字符串str，想通过添加字符的方式使得str整体都变成回文字符串，但要求只能在str的末尾添加字符，请返回在str后面添加的最短字符串 [举例] str = "abcd123321"，在必须包含最后一个字符的情况下，最长的回文子串是"123321"，之前不是最长回文子串的部分是'abcd"，所以末尾应该添加的部分就是"dcba"。 [要求] 如果str的长度为N，解决进阶问题的时间复杂度为O(N). 保证输入数据无回文串

输入描述:

输入为一个字符串str

输出描述:

输出一个字符串。

备注:

设N表示输入字符串的长度保证输入字符中只含有小写字母及数字