计算理论第二个实验,比第一个复杂,本机测试通过,可是ACM上总是说我的结果是错误的。郁闷中..
算法是动态规划,按照书上的伪码描述写出代码,不过还不理解为什么算法可行。关于伪码描述,可以在这里查看:CFG是P成员。
Problem description
上下文无关文法CFG G是否派生某个串W。采用动态规划(Dynamic Programming)设计一个一个多项式时间的验证算法。 实验方法: 编写一个算法/程序,对于给定的输入,可以在多项式时间内判定ACFG。 实验结果: 交一个程序验证。
Input
输入第一行为一个正整数n,接下来n行为一个满足乔姆斯基范式的文法描述。然后一个正整数m,接下来m行为m个小写字母组成的字符串(长度小于100) 表示m个待测试的串。
Output
对于没一个测试串返回"yes"或者"no",表示该串是否能被文法派生出来。
Sample Input
4
S->AB
A->AB|a
B->BC|b
C->CA|CC|c
3
ab
ac
bc
Sample Output
yes
no
no
本机测试结果
data.txt内容:
1 2 3 4 5 6 7 8 |
3 S->RT R->TR|a T->TR|b 3 baba ababb bbab |
table.html内容:
3 行CFG文法规则如下:
S->RT
R->TR|a
T->TR|b
3 个待测字符串为:
baba 长度 = 4
ababb 长度 = 5
bbab 长度 = 4
串baba表格为:
T | RT | S | SRT |
R | S | S | |
T | RT | ||
R |
串ababb表格为:
R | S | S | ||
T | RT | S | ||
R | S | |||
T | ||||
T |
串bbab表格为:
T | RT | S | |
T | RT | S | |
R | S | ||
T |
串 baba 接受状态: yes!
串 ababb 接受状态: no!
串 bbab 接受状态: yes!
31日更新
貌似是改了测试数据,有人ac了,不过我的代码却报超时。将内层循环移到外面之后,总算ac了。
下面是本机测试代码,稍加删除修改后即可提交。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 |
#include<cstdlib> #include<iostream> #include<fstream> using namespace std; int main() { ifstream fin; ofstream out; fin.open("data.txt"); int n,m; //n行满足乔姆斯基范式的文法描述, m行待测字符串 //while(cin>>n) //{ fin>>n; string *cfg; //CFG文法描述 cfg=new string[n]; for(int i=0;i<n;i++) fin>>cfg[i]; //输入CFG文法 fin>>m; //输入待测字符串数量 string *str; //待测字符串 str=new string[m]; for(int i=0;i<m;i++) fin>>str[i]; //输入待测字符串 int *lstr; //待测字符串的长度 lstr=new int[m]; for(int i=0;i<m;i++) lstr[i]=str[i].length(); string ***table; //定义表格 table=new string**[m]; for(int i=0;i<m;i++) table[i]=new string*[lstr[i]]; for(int i=0;i<m;i++) for(int j=0;j<lstr[i];j++) table[i][j]=new string[lstr[i]]; //输出测试 out.open("table.html",ios::app); out<<"<style>\ntable tr td {border: 1px solid blue; text-align: center;}\n</style>\n"; out<<"<hr />"<<n<<" 行CFG文法规则如下:<br />"; for(int i=0;i<n;i++) out<<cfg[i]<<"<br />"; out<<"<br />"<<m<<" 个待测字符串为:<br />"; for(int i=0;i<m;i++) out<<str[i]<<" 长度 = "<<lstr[i]<<"<br />"; out.close(); //找出所有A->b型规则 string Ab[100]; int num=0; for(int i=0;i<n;i++) { for(int k=3;k<cfg[i].length();k++) { if(cfg[i][k]>96 && cfg[i][k]<123) { Ab[num]+=cfg[i][0]; Ab[num]+=cfg[i][k]; num++; } } } cout<<"所有的A->b型规则为:"<<endl; for(int i=0;i<num;i++) cout<<Ab[i][0]<<"->"<<Ab[i][1]<<endl; //找出所有A->BC型规则 string ABC[100]; int num2=0; for(int i=0;i<n;i++) { for(int k=3;k<cfg[i].length();k++) { if(cfg[i][k]<91) { ABC[num2]+=cfg[i][0]; ABC[num2]+=cfg[i][k]; ABC[num2]+=cfg[i][k+1]; k++; num2++; } } } cout<<"所有A->BC型规则为:"<<endl; for(int i=0;i<num2;i++) cout<<ABC[i][0]<<"->"<<ABC[i][1]<<ABC[i][2]<<endl; //考察每一个长为1的子串 for(int i=0;i<m;i++) { for(int j=0;j<lstr[i];j++) //考察每一个长为1的子串 { for(int k=0;k<num;k++) { if(str[i][j]==Ab[k][1]) //考察CFG文法的每一个字符 table[i][j][j]=Ab[k][0]; } } } //考察l长度的子串 for(int i=0;i<m;i++) { for(int l=2;l<=lstr[i];l++) //l是子串的长度 { for(int p=0;p<lstr[i]-l+1;p++) //p是子串的起始位置 { int j=p+l-1; //j是子串的结束位置 for(int k=p;k<j;k++) //k是分裂的位置 k<=j-1 ->k<j { for(int q=0;q<num2;q++) { if(table[i][p][k].find(ABC[q][1],0)!=string::npos && table[i][k+1][j].find(ABC[q][2],0)!=string::npos) { table[i][p][j]+=ABC[q][0]; } } /*for(int kr=0;kr<n;kr++) { for(int c=cfg[kr].length()-1;c>2;c--) //考察CFG文法的每一个字符 { if(table[i][p][k].find(cfg[kr][c-1],0)!=string::npos && table[i][k+1][j].find(cfg[kr][c],0)!=string::npos) { out.open("gc.txt",ios::app); table[i][p][j]+=cfg[kr][0]; out<<"table["<<i<<"]["<<p<<"]["<<j<<"] = "<<table[i][p][j]<<endl; out.close(); } } }*/ } } } } for(int i=0;i<m;i++) { //打印表格 out.open("table.html",ios::app); out<<"<br />串"<<str[i]<<"表格为:"<<endl; out<<"<table border=\"2\" width=\"220px\">"<<endl; for(int row=0;row<lstr[i];row++) { out<<"<tr>"<<endl; for(int col=0;col<lstr[i];col++) { out<<"<td>"<<table[i][row][col]<<"</td>"; } out<<"</tr>"<<endl; } out<<"</table><br />"<<endl; out.close(); } //检查起始变元是否在table[0][n]中 for(int i=0;i<m;i++) { int flag=0; if(table[i][0][lstr[i]-1].find(cfg[0][0],0)!=string::npos) flag=1; if(flag==1) { cout<<"yes"<<endl; out.open("table.html",ios::app); out<<"<span style=\"font-weight:bold;\">串 "<<str[i]<<" 接受状态: <span style=\"color:red;\">yes!</span></span><br /><hr />"<<endl; out.close(); } else { cout<<"no"<<endl; out.open("table.html",ios::app); out<<"<span style=\"font-weight:bold;\">串 "<<str[i]<<" 接受状态: <span style=\"color:red;\">no!</span></span><br /><hr />"<<endl; out.close(); } } //释放数组 delete []cfg; delete []str; //释放表格 for(int i=0;i<m;i++) for(int j=0;j<lstr[i];j++) delete []table[i][j]; for(int i=0;i<m;i++) delete []table[i]; delete []table; fin.close(); //} system("pause"); return 0; } |
亲 能不能给出你的AC代码~实在是好难改啊