BOJ 18171 - ABB

BOJ 18171 - ABB

어떤 $i$ 에서 좌우로 가장 긴 팰린드롬의 길이가 가장 오른쪽 끝까지 닿을 때, 그 팰린드롬의 길이가 $\rm P$라면, $\lvert S \rvert - \rm P$ 개만 더 문자를 추가해서 팰린드롬을 만들어 줄 수 있다.

이걸 Manacher 알고리즘을 써서 빠르게 구한다음 정답에 min 연산을 해준다.

string transform(const string &s) {  
   string ret = "$";  
   for (int i = 0; i < sz(s); i++, ret += '$') ret += s[i];  
   return ret;  
}  
vi manacher(const string &s) {  
   int n = sz(s), p = 0;  
   vi ret(n);  
  
   for (int i = 1; i < n; i++) {  
      int r = p + ret[p];  
      if (r >= i) ret[i] = min(r - i, ret[2 * p - i]);  
      while (i - ret[i] - 1 >= 0 && s[i - ret[i] - 1] == s[i + ret[i] + 1])  
         ret[i]++;  
      if (i + ret[i] >= r) p = i;  
   }  
  
   return ret;  
}  
  
void solve() {  
   int n;  
   cin >> n;  
   string s;  
   cin >> s;  
   int ans = sz(s);  
   {  
      vi ret = manacher(s);  
      for (int i = 0; i < sz(s); i++) {  
         if (i + ret[i] == sz(s) - 1) {  
            ans = min(ans, sz(s) - (ret[i] * 2 + 1));  
         }  
      }  
   }  
   {  
      vi ret = manacher(transform(s));  
      for (int i = 0; i < sz(ret); i += 2) {  
         if (i + ret[i] == sz(ret) - 1) {  
            ans = min(ans, sz(s) - (ret[i] * 2 + 1) / 2);  
         }  
      }  
   }  
   cout << ans;  
}