ThePalindrome

문제

소문자로 구성된 1~50 글자의 임의의 문자열 s가 있다.

문자열 s 뒤에 0개 이상의 문자를 추가해 회문을 만든다.

이때 가장 짧은 회문의 길이를 리턴한다.

예시 입력

abab
abacaba
qwerty
abdfhdyrbdbsdfghjkllkjhgfds

예시 출력

5
7
11
38

생각의 변화

회문은 앞(->)과 뒤(<-)가 같은 문자열이다

가장 짧게 만든다는 건

반으로 잘라서 볼지 아니면

set< char > 을 확보해두고 s 뒤에 하나씩 붙이면서 -> <- 체크를 해볼까 했는데
이 방식은 문제가 있었다

거꾸로 문자열을 붙여야 하니, 자연스럽게 이런 생각을 했다.

qwerty
i   kj

if (s[i] != s[j])
    s += s[k]

하지만, 이 방식은 마지막 예시에서 오답이 나온다.
왜냐면 끝에 붙여야 하는건 s[k] 가 아니라 s[i] 기 때문이다.

따라서 역방향 접근이 필요하고, 문자열 중간에 문자를 삽입하고, 뒤의 문자들을 밀어주는 함수가 필요하다.

insert 함수를 사용한다.

pseudo code

find(s)
    i = 0
    last = i
    
    it = s.rbegin()
    n = s.size()
    
    while it != s.rend()
        if *it != s[i]
            s.insert(n, 1, s[last])
            last++
            
            // reset
            i=0
            it = s.rbegin()
        else
            i++
            it++
            
    return s.size()