string 앞에다가 최소한의 문자를 더해서 palindrome 만들기. 최소 갯수는?

일치하는 subfix와 postfix의 최대 길이를 물어보는건가?

bcacbc

aabbc

나이브하게는 하나씩 더하면서 팰린드롬인지 확인.. ( 무생각 )..

아아.. 왼쪽에서만 추가하니까.. 결국에는 오른쪽에 이상한게 있으면 전부 보충해줘야 한다.

즉, 뒤집은 문자열을 하나 만들고(이게 상한이다) 겹치는 만큼 줄인다.

abccd >> dccba abccd

bazcb

bczab >> 1개 겹치니까(뒤집은거의 앞에서부터) 4개 추가해서 bczabazcb로 만들 수 있다.

int findminadd(string s){

string t = s;

reverse(t.begin(),t.end());

int ret = 0;

while(s[ret]==t[ret]){

ret++;

}

return ret;

}

time complexity : O(N) ( 뒤집으니까 )

space complexity : O(N)