This code using a array palinIndex[i] to memory the longest palindrome string ended with i:
palinIndex[i] indicates string ended with s[i] and started with s[palinIndex[i]] is a palindrome, that is,
{palinIndex[i],...,i }construct a longest palindrome string.
How to caculate palinIndex:

just i, s[i] is a palindrome string,so palinIndex[i] = i;

s[i1]s[i] is palindrome ,so palinIndex[i] = i1;
 s[i2]s[i2]s[i] is palindrome ,so palinIndex[i] = i  2;
 {palinIndex[i1],...i1} is palindrome, so if s[palindrome[i1] 1] == s[i], palinIndex[i] = palinIndex[i]1;
 specially, for example "aaabcaaa". if palinIndex[i1] == palinIndex[i2], that is say {palinIndex[i1],...,i1} is same! so palinIndex[i] = palinIndex[i1],if s[i] == s[palinIndex[i1]];
All test case is passed! IS THIS RIGHT? I don't konw ,may I miss some case!
class Solution {
public:
string shortestPalindrome(string s) {
string str = "";
if(s.size() == 0)return str;
int palinIndex[s.size()];
int maxIndex = 0;
palinIndex[0] = 0;
for(int i = 1; i < s.size();i++){
int index = i;
if(i1 >= 0 && s[i] == s[i1]){
index = i  1;
}
if(i2 >= 0 && s[i] == s[i2]){
index = i  2;
}
if(palinIndex[i1]1 >= 0 && s[i] == s[palinIndex[i1]  1]){
index = min(index,palinIndex[i1]  1);
}
if(i > 2 && palinIndex[i1] == palinIndex[i2]){
if(s[i] == s[palinIndex[i1]]){
index = min(index,palinIndex[i1]);
}
}
palinIndex[i] = index;
if(index == 0){
maxIndex = i;
}
}
str = s.substr(maxIndex+1,s.size()  maxIndex);
reverse(str.begin(),str.end());
return str + s;
}
};