2179번: 비슷한 단어

https://www.acmicpc.net/problem/2179


$O(nl\lg n)$

문자열을 사전순 정렬을 한 뒤에 인접한 문자열끼리 비교하면 각 문자열의 최대 공통접두사 길이를 구할 수 있다.
...
s1
s2
s3
...
sn
...
(s1, s2), (s2,s3), ..., (sn-1,sn) 공통접두사 길이가 같으면 s1~sn 중 먼저 입력받은 두 문자열을 고려한다.
공통접두사 길이가 최대값인 먼저 입력받은 두 문자열을 출력한다.

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s[20000];
pair<string, int> p[20000];
pair<int, int> r, t;
int n, maxi = -1, pre = -1, l;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)cin >> s[i], p[i] = { s[i],i };
    sort(p, p + n);
    unique(p, p + n);
    for (int i = 1; i < n; i++) {
        for (l = 0; l<p[i - 1].first.size() && l<p[i].first.size() && p[i - 1].first[l] == p[i].first[l]; l++);
        if (l^pre) pre = l, t = { p[i - 1].second,p[i].second };
        else if (t.second > p[i].second) t.second = p[i].second;
        if (t.first > t.second) swap(t.first, t.second);
        if (maxi < l || maxi == l&&r>t) maxi = l, r = t;
    }
    cout << s[r.first] + '\n' + s[r.second];
    return 0;
}