| Problem 12595 : No special judgement |
| Problem description |
| ADFA={< B,w >|B是DFA，w是串，B接收w}证明：ADFA是可判定的。 实验方法:编写一个算法/程序，对于任意给定的输入<b,w>，可以判定ADFA。 |
| Input |
| 有多个测试序列，测试结束于测试文件结束； 每个测试序列的第一行为几个正整数n m t a分别表示有n个状态，从a开始m个小写字母组成的字符集，第一个状态默认为起始状态。t个接受状态和a个测试串,接下来为一个n行m列的矩阵S,其中S[i][j]表示第i行第j列，意义为状态i经过字母j到达状态S[i][j]。接下来有t个数字,表示t个接受状态值，然后是a行，每行一个串表示待测试的串。 |
| Output |
| 对于每个字符串输出YES表示该DFA接受该串，NO表示不接受。 |
| Sample Input |
3 3 1 2 2 3 2 3 3 3 3 3 3 2 a b |
| Sample Output |
YES NO |
代码如下：
#include <iostream>
#include <cstring>
using namespace std;
long n,m,t,a;
long s[1000][1000],accept[1000];
int main(){
while(cin>>n>>m>>t>>a){
memset(s,0,sizeof(s));
memset(accept,0,sizeof(accept));
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++)
cin>>s[i][j];
}
for(int i = 0;i<t;i++){
long temp;
cin>>temp;
accept[temp] = 1;
}
while(a--){
string temps;
cin>>temps;
int after = 1;
for(int i = 0;i<temps.length();i++){
after = s[after][temps[i]-‘a‘+1];
}
if(accept[after]==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}
本博文属原创，转载请声明！
原文：http://www.cnblogs.com/pengfeiz/p/5123718.html