## DFA 识别语言

Time Limit: 1sec Memory Limit:256MB

### Sample Input

4 2
1 0
1 2
1 3
1 0
3 -1
aaabb
abbab
abbaaabb
abbb
#
1 3
0 0 0
0 -1
cacba
#
0 0


### Sample output

YES
NO
YES
NO
YES


### Solution

#include <bits/stdc++.h>
using namespace std;
struct DeterministicFiniteAutomaton
{
struct State
{
vector<int> trans;
int isAccepted;
State(int m) : trans(m, -1), isAccepted(0) {}
};
vector<State> state;
DeterministicFiniteAutomaton(int n, int m) : state(n, State(m)) {}
{
int cur = 0;
for (int i = 0; i < s.size(); ++i)
{
cur = state[cur].trans[s[i] - 'a'];
if (cur < 0)
return 0;
}
return state[cur].isAccepted;
}
};
int main()
{
for (int n, m; cin >> n >> m && n && m;)
{
DeterministicFiniteAutomaton dfa(n, m);
for (int i = 0, k; i < n; ++i)
for (int j = 0; j < m; ++j)
{
cin >> k;
dfa.state[i].trans[j] = k;
}
for (int k; cin >> k && k >= 0;)
dfa.state[k].isAccepted = 1;
for (string s; cin >> s && s != "#";)
cout << (dfa.ask(s) ? "YES\n" : "NO\n");
}
}


## NFA 识别语言

Time Limit: 1sec Memory Limit:256MB

### Sample Input

4 3
{} {0,1} {0}
{} {} {2}
{} {} {3}
{} {} {}
3 -1
aaabb
abbab
abbaaabb
abbb
#
0 0


### Sample Output

YES
NO
YES
NO


### Solution

#include <bits/stdc++.h>
using namespace std;
struct NondeterministicFiniteAutomaton
{
struct State
{
vector<vector<int>> trans;
int isAccepted;
State(int m) : trans(m), isAccepted(0) {}
};
vector<State> state;
NondeterministicFiniteAutomaton(int n, int m) : state(n, State(m)) {}
vector<vector<int>> vis;
int ask(const string &s, int i = 0, int cur = 0)
{
if (vis[i][cur])
return 0;
vis[i][cur] = 1;
if (i == s.size() && state[cur].isAccepted)
return 1;
for (int j : state[cur].trans.back())
return 1;
if (i < s.size())
for (int j : state[cur].trans[s[i] - 'a'])
if (ask(s, i + 1, j))
return 1;
return 0;
}
};
int main()
{
for (int n, m; cin >> n >> m && n && m;)
{
NondeterministicFiniteAutomaton dfa(n, m);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
string s;
cin >> s;
int x = -1;
for (int k = 1; k < s.size(); ++k)
{
if (isdigit(s[k]))
{
if (x < 0)
x = 0;
x = x * 10 + s[k] - '0';
}
else if (x >= 0)
{
dfa.state[i].trans[(j + m - 1) % m].push_back(x);
x = -1;
}
}
}
for (int k; cin >> k && k >= 0;)
dfa.state[k].isAccepted = 1;
for (string s; cin >> s && s != "#";)
{
dfa.vis.assign(s.size() + 1, vector<int>(n, 0));
cout << (dfa.ask(s) ? "YES\n" : "NO\n");
}
}
}