Note: This article is available in Chinese only. 本文暂无英文版本。
View original
1/*************************************************************************
2 > File Name: code/cf/#315/E.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月15日 星期六 13时48分36秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#define y0 abc111qqz
20#define y1 hust111qqz
21#define yn hez111qqz
22#define j1 cute111qqz
23#define tm crazy111qqz
24#define lr dying111qqz
25using namespace std;
26#define REP(i, n) for (int i=0;i<int(n);++i)
27typedef long long LL;
28typedef unsigned long long ULL;
29const int inf = 0x7fffffff;
30const int N=5E2+7;
31int flag[N],flag2[N];
32int f[N][N];
33int a[N];
34char s[N];
35int ans[N];
36int len,n,m;
37char s1[13],s2[13];
38int p1,p2,q1,q2,dq1,dq2;
39void add(int p,int q,int flag[])
40{
41 int dq = q * n + p;//找到元辅音状态为q，第p的点的下标
42 for (int i=1;i<=2*n;++i)
43 {
44 if (f[dq][i]==0) continue;
45 flag[i]=1;//找到所有由dp出发的边指向的点，表示选了dp点一定要选的点。
46 }
47}
48bool check(int flag[])
49{
50 for (int i=1;i<=n;++i)
51 if (flag[i]==1&&flag[i+n]==1) return false; //判断是否存在矛盾
52 //（选了j点后，既要选择某点k的元音，也要选择某点k的辅音）
53 return true;
54}
55bool dfs(int pos,int x)
56{
57 if (pos>n) return true;//如果能形成一个长度为n的单词，说明这种语言有word
58 bool g[2];
59 g[0]=g[1]=false;
60 for (int i=x;i<=len;++i)//从当前字母x往后枚举
61 {
62 for (int j=1;j<=2*n;++j) flag2[j]=flag[j];//为了不影响原始数组，复制一个布尔数组出来。
63 add(pos,a[i],flag2);//找到所有选了pos点一定要选的点
64 if (check(flag2)&&(!g[a[i]]))
65 {
66 g[a[i]]=true;
67 for (int j=1;j<=2*n;++j) flag[j]=flag2[j];
68 ans[pos]=i;//将第pos位置的字母变成i
69 if (dfs(pos+1,1)) return true;
70 else return false;//只要有一位找不到合适的字母形成单词，那么肯定就构不成单词。
71 }
72 }
73 return false;
74}
75int main()
76{
77 scanf("%s",s);
78 len=strlen(s); //0表示辅音，１表示原因，下同。
79 for (int i=1;i<=len;++i)//len 表示字母表中一共有的字母的个数
80 {
81 if (s[i-1]=='V')
82 {
83 a[i] = 0;
84 }
85 else
86 {
87 a[i] = 1;
88 }
89 }
90 memset(f,0,sizeof(f));
91 scanf("%d%d",&n,&m);
92 for (int i=1;i<=m;++i)//1..n表示元音的点，n+1..2*n 表示辅音的点
93 {
94 scanf("%d",&p1);
95 scanf("%s",s1);
96 if (s1[0]=='V') q1=0;else q1=1;
97 scanf("%d",&p2);
98 scanf("%s",s2);
99 if (s2[0]=='V') q2=0;else q2=1;
100 dq1=q1*n+p1;dq2=q2*n+p2;//找到这组关系对应的点。
101 f[dq1][dq2]=1;//连一条由dq1指向dq2的边，表示如果选了dp1点，那么一定选dp2点
102 dq1=(1-q2)*n+p2;dq2=(1-q1)*n+p1;//找到逆否命题对应的点
103 // （"如果选１，一定选２"的逆否命题是，"如果不选２，一定不选１"）
104 f[dq1][dq2]=1; //在连一条边
105 }
106 for (int i=1;i<=2*n;++i) f[i][i]=1;
107 for (int k=1;k<=2*n;++k)//floyd ，把所有间接相连的边直接相连
108 {
109 for (int i=1;i<=2*n;++i)
110 for (int j=1;j<=2*n;++j)
111 f[i][j]|=f[i][k]&f[k][j];
112 }
113 scanf("%s",s+1);
114 bool ok=false;
115 for (int i=n;i>=0;--i) //倒着扫，每次只改变最后一位的字母，字母从小往大枚举 //这样就可以保证字典序最小。
116 {
117 memset(flag,0,sizeof(flag));
118 for (int j=1;j<=i;++j)
119 {
120 add(j,a[s[j]-'a'+1],flag);
121 ans[j]=s[j]-'a'+1;
122 }
123 if (!check(flag)) continue;
124 if (dfs(i+1,s[i+1]-'a'+1+1))
125 {
126 ok=true;
127 break;
128 }
129 }
130 if (!ok) printf("-1\n");
131 else
132 {
133 for (int i=1;i<=n;++i) printf("%c",ans[i]+'a'-1);
134 }
135 return 0;
136}