题解 | #字符串排序#

#include <bits/stdc++.h>
using namespace std;

int T, q, n, t[3000005][65], cnt[3000005], idx;
char s[3000005];

int getnum(char x) {
    if (x >= 'A' && x <= 'Z')
        return x - 'A';
    else if (x >= 'a' && x <= 'z')
        return x - 'a' + 26;
    else
        return x - '0' + 52;
}

void insert(char str[]) {
    int p = 0, len = strlen(str);
    for (int i = 0; i < len; i++) {
        int c = getnum(str[i]);
        if (!t[p][c])
            t[p][c] = ++idx;
        p = t[p][c];
    }
    cnt[p]++;
}

int find(char str[]) {
    int p = 0, len = strlen(str);
    for (int i = 0; i < len; i++) {
        int c = getnum(str[i]);
        if (!t[p][c])
            return 0;
        p = t[p][c];
    }
    return cnt[p];
}

void pr(int node, string& cur) {
    while (cnt[node] > 0) {
        cout << cur << endl;
        cnt[node]--;
    }

    for (int i = 0; i < 65; i++) {
        if (t[node][i] != 0) {
            char ch = ' ';
            if (i < 26) {
                ch = 'A' + i;
            } else if (i < 52) {
                ch = 'a' + i - 26;
            } else {
                ch = '0' + i - 52;
            }

            cur.push_back(ch);
            pr(t[node][i], cur);
            cur.pop_back();
        }
    }
}

int main() 
{
	scanf("%d", &n);
    for (int i = 0; i <= idx; i++)
        for (int j = 0; j <= 122; j++)
            t[i][j] = 0;
    for (int i = 0; i <= idx; i++)
        cnt[i] = 0;
    idx = 0;
    
    for (int i = 1; i <= n; i++) 
	{
        scanf("%s", s);
        insert(s);
    }
    // 输出字典树的先序遍历结果
    string cur = "";
    pr(0, cur);
    
    return 0;
}