[BOJ] 3178 코코스

반으로 잘라서 정렬을 한 후, 인접한 두 문자열의 겹치는 접두사의 길이만큼 트라이에서 정점이 감소하는 것이므로 n * k에서 길이만큼을 빼주면 된다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,k;
vector<string> s;
vector<string> e;

int cmp(string a, string b,string c, string d){
    int i = 0, j = 0;
    if(a == b) i = k;
    else while(a[i] == b[i]) ++i;
    if(c == d) j = k;
    else while(c[j] == d[j]) ++j;
    return i + j;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i = 0; i < n; i++){
        string str; cin>>str;
        s.push_back(str.substr(0,k));
        string t = str.substr(k,2*k);
        reverse(t.begin(), t.end());
        e.push_back(t);
    }
    int ans = n * k * 2;
    sort(s.begin(),s.end());
    sort(e.begin(),e.end());
    for(int i = 1; i < n; i++) ans -= cmp(s[i-1],s[i],e[i-1],e[i]); 
    cout<<ans;
    return 0;
}