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.

For example:

Given"aacecaaa", return"aaacecaaa".

Given"abcd", return"dcbabcd".

Brute Force idea: check for matching substrings

Ex1:

abcd
dcba
abc
cba
ab
ba
a
a

Ex2:
adcbabcd
aacecaaa
aaacecaa
aacecaa
aacecaa

string shortestPalindrome(string s) {
    string r = s;
    reverse(r.begin(), r.end());

    const size_t size = s.length();
    int i = 0;
    for (i; i < size; i++) {
        if (s.substr(0, size - i) == r.substr(i))
            break;
    }

    return r.substr(0, i) + s;
}


int main()
{
    cout << shortestPalindrome("abcd") << endl;
    cout << shortestPalindrome("aacecaaa") << endl;
}