import (
	"strings"
)

func shortestPalindrome(s string) string {
	l := len(s)
	if l <= 1 {
		return s
	}
	var i, j int
	for i = l; i <= 2*l; i++ { // i means the length of the shortest palindrome
		if i%2 == 1 { // Odd
			for j = 1; 0 <= l-1-i/2-j && s[l-1-i/2-j] == s[l-1-i/2+j]; j++ {
			}
			if l-1-i/2-j < 0 {
				break
			}
		} else { // Even
			for j = 1; 0 <= l-i/2-j && s[l-i/2-j] == s[l-1-i/2+j]; j++ {
			}
			if l-i/2-j < 0 {
				break
			}
		}
	}
	idx := l - 1 - i/2 + j
	var ans strings.Builder
	for i := l-1; idx <= i; i-- {
		ans.WriteByte(s[i])
	}
	ans.WriteString(s)
	return ans.String()
}