BOJ 10096 - 세 친구
이 홀수가 아니면 불가능하다.
이라고 하자.
이다.
이제 와 에서 언제까지 앞의 개수가 일치하는지 보자.
더이상 일치하지 않는 지점을 라고 하자.
가 의 길이와 같다면 처럼 중앙에 하나가 다른 경우이므로 가 로 가능하다.
그렇지 않다면 에서 부터의 부분문자열과 에서 부터의 부분문자열이 같은지 보자.
같다면 부분이 다른 한 문자가 되고 가 로 가능하다.
로 될 수 있는 두 가지를 모두 검사하고 둘다 정답이 안된다면 불가능하고 하나만 되거나 둘이 같다면 그것이 이고 두개가 다르다면 유일하지 않다.
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";
}
}
Comments