算法
(构造、字符串数组排序) $O(N\log N)$
我们可以给原字典序和新字典序之间构造两个映射 $f$ 和 $g$
f
:从新字典序映射到原字典序
g
:从原字典序映射到新字典序
对于给定的字符串数组,我们可以先利用映射 $f$ 把所有的字符串切换到原字典序
再利用 std::sort
对字符串数组排序
然后把排序后的字符串数组利用映射 g
切换到新字典序
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::vector;
using std::string;
int main() {
string x;
int n;
cin >> x >> n;
vector<string> s(n);
rep(i, n) cin >> s[i];
map<char, char> f, g;
rep(i, 26) f[x[i]] = 'a' + i;
rep(i, 26) g['a' + i] = x[i];
rep(i, n) for (char& c : s[i]) c = f[c];
sort(s.begin(), s.end());
rep(i, n) for (char& c : s[i]) c = g[c];
rep(i, n) cout << s[i] << '\n';
return 0;
}