计算理论第二个实验，比第一个复杂，本机测试通过，可是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内容：

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表格为：

串ababb表格为：

串bbab表格为：

串 baba 接受状态: yes!

串 ababb 接受状态: no!

串 bbab 接受状态: yes!

31日更新

貌似是改了测试数据，有人ac了，不过我的代码却报超时。将内层循环移到外面之后，总算ac了。
下面是本机测试代码，稍加删除修改后即可提交。

#include
#include
#include
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>cfg[i];		//输入CFG文法
		fin>>m;					//输入待测字符串数量
		string *str;			//待测字符串
		str=new string[m];
		for(int i=0;i>str[i];		//输入待测字符串
		
		int *lstr;				//待测字符串的长度
		lstr=new int[m];
		for(int i=0;i\ntable tr td {border: 1px solid blue; text-align: center;}\n\n";
		out<<"
"<";
		for(int i=0;i";
		out<<"
"<";
		for(int i=0;i";
		out.close();
		
		//找出所有A->b型规则
		string Ab[100];
		int num=0;
		for(int i=0;i96 && cfg[i][k]<123)
				{
					Ab[num]+=cfg[i][0];
					Ab[num]+=cfg[i][k];
					num++;
				}
			}
		}
		cout<<"所有的A->b型规则为："<"<BC型规则
		string ABC[100];
		int num2=0;
		for(int i=0;iBC型规则为："<"<k2;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["<串"<"<"<"<";
				}					
				out<<""<
"<串 "<yes!
"<串 "<no!
"<


相关文章:

计算理论实验—ADFA的可判定性 
计算理论笔记 
用stringstream进行类型转换 
C++输出16进制数和整行读取文件 
C++处理命令行选项 
美团2014校招笔试