BOJ 10096 - 세 친구

BOJ 10096 - 세 친구

$N$이 홀수가 아니면 불가능하다.

$wlog.$ $a=U_{[0,\left\lfloor N/2 \right\rfloor]},~~b=U_{[\left\lfloor N/2 \right\rfloor+1,N-1]}$ 이라고 하자.

$\lvert a \rvert=\lvert b \rvert+1$ 이다.

이제 $a$와 $b$에서 언제까지 앞의 개수가 일치하는지 보자.

더이상 일치하지 않는 지점을 $i$ 라고 하자.

$i$ 가 $b$ 의 길이와 같다면 $ABCXABC$ 처럼 중앙에 하나가 다른 경우이므로 $b$ 가 $S$로 가능하다.

그렇지 않다면 $a$에서 $i+1$ 부터의 부분문자열과 $b$ 에서 $i$ 부터의 부분문자열이 같은지 보자.

같다면 $i$ 부분이 다른 한 문자가 되고 $b$가 $S$로 가능하다.

$a, b$ 로 될 수 있는 두 가지를 모두 검사하고 둘다 정답이 안된다면 불가능하고 하나만 되거나 둘이 같다면 그것이 $S$ 이고 두개가 다르다면 유일하지 않다.

void solve() {  
   int n;  
   cin >> n;  
   string s;  
   cin >> s;  
   if (n % 2 == 0) {  
      cout << "NOT POSSIBLE";  
      return;  
   }  
   int m = n / 2;  
   string a = s.substr(0, m + 1);  
   string b = s.substr(m + 1);  
  
   auto chk = [&](string a, string b) -> string {  
      int i = 0;  
      for (; i < sz(b); i++) {  
         if (a[i] == b[i]) continue;  
         else {  
            break;  
         }  
      }  
      if (i == sz(b)) {  
         return b;  
      }  
      if (a.substr(i + 1) == b.substr(i)) {  
         return b;  
      }  
  
      return "";  
   };  
   string ret1 = chk(a, b);  
  
   a = s.substr(0, m);  
   b = s.substr(m);  
   string ret2 = chk(b, a);  
   if (ret1 == "" && ret2 == "") {  
      cout << "NOT POSSIBLE";  
   } else if (ret1 == "") {  
      cout << ret2;  
   } else if (ret2 == "") {  
      cout << ret1;  
   } else if (ret1 == ret2) {  
      cout << ret1;  
   } else {  
      cout << "NOT UNIQUE";  
   }  
}