algorithm
[BOJ] 3178 코코스
fungod
2022. 8. 23. 00:18
반으로 잘라서 정렬을 한 후, 인접한 두 문자열의 겹치는 접두사의 길이만큼 트라이에서 정점이 감소하는 것이므로 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;
}