字典树+map

Problem Description
Carryon最近喜欢上了一些奇奇怪怪的字符，字符都是英文小写字母，但奇怪的是a可能比b小，也可能比b大，好奇怪。与此同时，他拿到了好多的字符串，可是看着很不顺眼，因为他们很乱，所以他想将这些字符串按字典序从小到大排下序，这样就好看多了。由于a可能比b小，也可能比b大，这样按常规方法肯定是不行的，幸运的是他破解了26个字母的大小顺序，这样他就开开心心的将字符串从小到大排序了。

Input
第一行输入26个字符的大小顺序

第二行输入一个n(1≤n≤105)。

接下来n行，每行一个字符串si，数据保证每个字符串不重复。(1≤∑i = 1nlen(si)≤3×105)
Output
将n个字符串按字典序从小到大输出。

Sample Input
abcdefghijklmnopqrstuvwxyz
5
bcda
licj
lin
aaaa
aaaaa
Sample Output
aaaa
aaaaa
bcda
licj
lin

  1 #include<iostream>
  2 #include<string.h>
  3 #include<algorithm>
  4 #include<map>
  5 #define maxn 1111111
  6 using namespace std;
  7 int pos = 1;
  8 char s[26], str[maxn];
  9 int t[maxn][26];
 10 bool vis[maxn];
 11 map<char, int>mm;
 12 void insert(char *s)
 13 {
 14     int rt = 0, len = strlen(s);
 15     for (int i = 0; i<len; i++)
 16     {
 17         int x = mm[s[i]];
 18         if (!t[rt][x])//如果没有从rt到x的字符串前缀，插入一个
 19             t[rt][x] = pos++;//按查询字符串的每个字符输入顺序进行标记
 20         rt = t[rt][x];//为下一次标记准备，将当前节点作为下一次标记的上一个节点
 21     }
 22     vis[rt] = 1;//在每次输入的一个字符串的最后一个字符标记
 23 }
 24 void dfs(int rt, int deep)
 25 {
 26     for (int i = 0; i<26; i++)//从第一个字符开始找（第一个字符就是最小的）
 27     {
 28         if (t[rt][i])//如果有从rt到i的字符串前缀
 29         {
 30             str[deep] = s[i];//str[]记录s[i]字符串
 31             if (vis[t[rt][i]])//搜到s[]串的最后一个字符就输出这个字符串
 32             {
 33                 str[deep + 1] = '';//''字符串结束符，字符串的结束标志
 34                 printf("%s
", str);
 35             }
 36             dfs(t[rt][i], deep + 1);
 37         }
 38     }
 39     return;
 40 }
 41 int main()
 42 {
 43     scanf("%s", s);
 44     for (int i = 0; i<26; i++)
 45         mm[s[i]] = i;
 46     int n;
 47     scanf("%d", &n);
 48     memset(vis, 0, sizeof(vis));
 49     for (int i = 0; i<n; i++)
 50     {
 51         char ss[3333333];
 52         scanf("%s", ss);
 53         insert(ss);
 54     }
 55     dfs(0, 0);
 56     return 0;
 57 }





 58 #include<iostream>
 59 #include<cstring>
 60 #include<algorithm>
 61 #include<string>
 62 #include<map>
 63 #define N 100005
 64 using namespace std;
 65 map<char, char>m;
 66 struct node
 67 {
 68     string s;//s是输入的字符串
 69     string ss;//ss是映射之后的字符串
 70 }str[N];
 71 bool cmp(node a, node b)
 72 {
 73     return a.ss<b.ss;
 74 }
 75 int main()
 76 {
 77     char New[100];
 78     scanf("%s", New);
 79     for (int i = 0; i<26; i++)
 80     {
 81         m[New[i]] = 'a' + i;//构建映射
 82     }
 83     int n;
 84     scanf("%d", &n);
 85     for (int i = 0; i<n; i++)
 86     {
 87         cin >> str[i].s;
 88         int len = str[i].s.length();
 89         for (int j = 0; j<len; j++)
 90         {
 91             str[i].ss += m[str[i].s[j]];//使用上面的映射关系
 92         }
 93     }
 94     sort(str, str + n, cmp);
 95     for (int i = 0; i<n; i++)
 96     {
 97         cout << str[i].s << endl;
 98     }
 99     return 0;
100 }