この投稿で説明するように、非決定性有限オートマトンをシミュレートするための割り当てを行っています。この入力をファイルから読み取らせますtarea4.in：
1
6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
5
aaabcccc
aabbbbcdc
abbcdddcc
acdddddd
abc
入力の最初の行は整数Tで、プログラムを評価するケースの数を表します。各テストケースは4つの整数で始まり、最初はオートマトンの状態の数、次はオートマトンの遷移の数、3番目の数は初期状態、そして最後の状態の数です。次に、最終状態が発生します（この例では、最終状態は2と5です）。次に、Eが最終状態であることを表す整数Eを持つF行が来ます。
次に、N行（Nは遷移の数）が来ます。それぞれ2つの整数と、遷移、つまり遷移が状態iから状態Jに文字Cで進む状態を表す文字I、J、およびCがあります。この行の後には、テストする文字列の数を含む単一の整数Sが続き、次にそれぞれの文字列を含むS行が続きます。
期待される出力は次のとおりです。
Test Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Accepted
abc Accepted
私のコードに帰着する出力：
Test Case #1:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Rejected
abc Rejected
これが私のコードです：
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <vector>
using namespace std;
typedef map<pair<int, int>, char> transitions;
transitions trans;
int numberFinals;
vector<int> currentStates;
int main (){
freopen ("tarea4.in", "r", stdin);
//freopen ("tarea4.out", "w", stdout);
int testCases, i, j,k, cont=1,finalStates,numberInputs,stateOrigin, stateDestination;
int numberStates, numberTransitions, initialState;
char transitionCharacter ;
set<int> current;
set<int> next;
set<int>::iterator it;
set <int> final;
std::set<int> the_intersection; // Destination of intersect
map<pair<int, int>, char>::iterator p;
string inputString;
cin>> testCases;
for (i=0;i< testCases;i++){
cin>>numberStates>>numberTransitions>>initialState>>numberFinals;
current.insert (initialState);
for (j=0;j<numberFinals;j++){
cin>>finalStates;
final.insert(finalStates);
}
for (j=0; j<numberTransitions;j++){
cin>> stateOrigin>>stateDestination>>transitionCharacter;
trans.insert(transitions::value_type(std::make_pair(stateOrigin, stateDestination), transitionCharacter ));
}
cin>>numberInputs;
cout<<"Test Case #"<<cont++<<":"<<endl;
for (j=0; j<numberInputs;j++){
//////////////////the code of the answer /////////////////
current.insert (initialState);
cin>> inputString;
cout<<inputString<<" ";
for (k=0; k<str.size();k++){
next.clear();
for ( it=current.begin() ; it != current.end(); it++ ){
for (q= trans.begin(); q!= trans.end();q++){
if((*it == q->first.first)&&(str[k]==q->second)){
next.insert(q->first.second);
}
current=next;
}
}
}
std::set_intersection(current.begin(), current.end(), final.begin(), final.end(), std::inserter(the_intersection, the_intersection.end()));
if (the_intersection.size()>0){
cout<< "Accepted"<<endl;
}
else{
cout<< "Rejected"<<endl;
}
}
printf ("\n");
}
return 0;
}
私の質問は：なぜ私は間違った出力を得るのですか？テストケースで定義されたオートマトンの非決定性のためだと思いますが、文字列を正しく評価するにはどうすればよいですか？呼び出された関数evaluate_stringを何らかの方法で変更して、非決定論によって文字列を評価するためにオートマトンを使用できるさまざまなパスを確認するにはどうすればよいですか？
私はこれに数日間立ち往生していて、正直に言うと私はやや必死です。