1 #include <iostream>
2 using namespace std;
3 #include <cstdio>
4 #include <cstdlib>
5 #include <cmath>
6 int qm[27],sd[27],dy[27];// qm记录入度
7 string s[50001];
8 int next[1000],back[1000],last[1000];//邻接表元素
9 bool yt[27][27];// 判断字母应该出现的顺序
10 int tot,cmax;
11 bool cx[27];
12 void add_edge(int a,int b)
13 {
14 tot++;
15 next[tot]=b;// 记录能够到达的边 也就是说b 必须要在 a 之后才能出现
16 back[tot]=last[a];// 指针指向下一条边
17 last[a]=tot;// 相当于head指针
18 }
19 void dfs(int x,int t)// t表示字母个数
20 {
21 if (t>sd[x]) sd[x]=t; //sd表示与x相关的字母数量
22 int i=last[x];
23 while (i!=0)// 枚举与x+96相关的所有字母
24 {
25 int v=next[i];
26 if (sd[v]<=t) dfs(v,t+1);
27 i=back[i];
28 }
29 }
30 void error()
31 {
32 cout<<"0";
33 exit (0);// 退出程序 相当于return 0；
34 }
35 int main()
36 {
37 int k;
38 cin>>k;
39 for (int i=0; i<=k; i++)
40 getline(cin,s[i]);//读入数据
41 for (int i=2; i<=k; i++)// 因为判断是把当前字符串与上一个字符串进行比较 故从2开始
42 {
43 int l1=s[i-1].size();
44 int l2=s[i].size(); //保存两个字符串的长度，方便进行for循环
45 for (int j=0; j<=min(l1,l2)-1; j++) //比较到较小长度即可 多了无意义
46 {
47 int t1=s[i-1][j]-96;// -96是把字符转换成数字，方便yt数组的判断 97是a的码 减去96是为了让最小的元素为1 方便进行数组判断
48 int t2=s[i][j]-96;//同理
49 cmax=max(t1,max(t2,cmax));// 找到所有输入的最大值
50 if (t1==t2) continue; // 如果是相同的话不需要进行判断
51 if (yt[t2][t1]) error();// 因为根据题目要求的字典序输入 故t1必须在t2之前 否则出差
52 qm[t2]++;// t2的入度++ 拓扑排序
53 yt[t1][t2]=true;//
54 add_edge(t1,t2);// 都懂
55 break;// 如果找到t1<t2的元素直接退出 因为字典序只比较第一个不相同的元素
56 }
57 }
58 for (int i=1; i<=cmax; i++)
59 {
60 if (qm[i]==0) //入度为0
61 dfs(i,1); // i+96表示进行搜索的字母
62 }//统计与所有字母相关的字母的数量
63 string que,ans="";
64 getline(cin,que);// 输入待处理的字符串
65 for (int i=0; i<=que.size()-1; i++)
66 {
67 if (cx[sd[que[i]-96]]) error();
68 cx[sd[que[i]-96]]=true; //判重？？？
69 if (sd[que[i]-96]==0) error();//没有找到可以匹配的元素
70 ans=ans+(char (sd[que[i]-96]+96));
71 }
72 cout<<ans;
73 //个人感觉sd数组有一个妙用
74 //就是因为题目的性质，
75 //所以每个与字母相连的字母的个数肯定不相同
76 //否则错误
77 //根据这一性质我们可以找出每一个字母对应的字母
78 }