| Problem description |
| 上下文无关文法CFG G是否派生某个串W。采用动态规划（Dynamic Programming）设计一个一个多项式时间的验证算法。 实验方法： 编写一个算法/程序，对于给定的输入<g,w>，可以在多项式时间内判定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 |
代码如下：
#include<cstdlib>
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
int n,m;
while(cin>>n)
{
string *cfg;
cfg=new string[n];
for(int i=0;i<n;i++)
cin>>cfg[i];
cin>>m;
string *str;
str=new string[m];
for(int i=0;i<m;i++)
cin>>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]];
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++;
}
}
}
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++;
}
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<lstr[i];j++)
{
for(int k=0;k<num;k++)
{
if(str[i][j]==Ab[k][1])
table[i][j][j]=Ab[k][0];
}
}
}
for(int i=0;i<m;i++)
{
for(int l=2;l<=lstr[i];l++)
{
for(int p=0;p<lstr[i]-l+1;p++)
{
int j=p+l-1;
for(int k=p;k<j;k++)
{
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 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;
}
else
{
cout<<"no"<<endl;
}
}
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;
}
return 0;
}
原文：http://www.cnblogs.com/pengfeiz/p/5123730.html