题目理解

本题要求判断给定的字符串是否属于某个上下文无关文法（$\text{Context-Free Grammar}$, $\text{CFG}$）生成的语言，且该文法已转换为乔姆斯基范式（$\text{Chomsky Normal Form}$, $\text{CNF}$） 。
$\text{CNF}$ 文法中的所有产生式规则只有两种形式：

1. $A\to BC$ （其中 $A,B,C$ 均为非终结符）
2. $A\to a$ （其中 $A$ 为非终结符，$a$ 为终结符）

给定一个 $\text{CNF}$ 文法（包括根符号、非终结符集、终结符集、产生式规则）和若干个候选字符串，我们需要对每个候选字符串输出它是否属于该文法生成的语言 $L(G)$ 。

---

算法选择：$\text{CYK}$ 算法

由于 CNF 形式具有很好的结构性质，我们可以使用 $\text{CYK}$ 算法（$\text{Cocke–Younger–Kasami}$） 来解决这个问题。
$\text{CYK}$ 算法是一种基于动态规划的算法，专门用于判断给定字符串是否属于某个 $\text{CNF}$ 文法生成的语言。

$\text{CYK}$ 算法核心思想

设候选字符串 $s$ 的长度为 $n$ 。我们定义一个二维表 $dp[i][j]$ ，它表示子串 $s[i\dots j]$ 可以由哪些非终结符推导出来（即存在至少一种推导方式从该非终结符出发得到这个子串）。

1. 初始化（长度为 1 的子串）

对于每个位置 $i$ （$0\le i<n$），考虑单个字符 $s[i]$ 。
我们检查所有形如 $A\to a$ 的产生式，如果 $a=s[i]$ ，那么 $A$ 就可以推导出子串 $s[i\dots i]$ 。
因此，将 $A$ 加入 $dp[i][i]$ 中。

2. 动态规划递推（长度 > 1 的子串）

对于长度 $len=2\dots n$ 的子串 $s[i\dots j]$ （其中 $j=i+len-1$），我们尝试所有可能的分割点 $k$ （$i\le k<j$），将子串分为两部分：

• 左部分：$s[i\dots k]$
• 右部分：$s[k+1\dots j]$

假设左部分可以由非终结符 $B$ 推导出，右部分可以由非终结符 $C$ 推导出，即 $B\in dp[i][k]$ ，$C\in dp[k+1][j]$ 。
那么，如果存在产生式 $A\to BC$ ，则 $A$ 就可以推导出整个子串 $s[i\dots j]$ 。
因此，将所有这样的 $A$ 加入 $dp[i][j]$ 中。

3. 判断结果

最后，检查根符号 $S$ 是否在 $dp[0][n-1]$ 中。
如果在，说明整个字符串 $s$ 可以由根符号推导出，即 $s\in L(G)$ ；否则， $s\notin L(G)$ 。

---

复杂度分析

• 时间复杂度：$O(n^3\cdot |P|)$ ，其中 $n$ 是字符串长度， $|P|$ 是产生式数量。由于 $n\le 50$ ，该复杂度是可接受的。
• 空间复杂度：$O(n^2\cdot |V|)$ ，用于存储 $dp$ 表。

---

实现细节

1. 输入处理

输入格式比较固定，但需要注意：

• 每个测试用例以根符号开始。
• 产生式规则以 # -> # 结束。
• 候选字符串列表以 # 单独一行结束。
• 输入中可能有空行，需要适当处理。

2. 数据结构设计

• 使用 map<char, vector<string>> toTerminal 存储 $A\to a$ 类型的产生式，便于根据终结符查找非终结符。
• 使用 map<string, vector<char>> toNonTerminal 存储 $A\to BC$ 类型的产生式，键为字符串 “$BC$” ，值为可以推导出它的非终结符列表。
• 使用 set<char> 存储 $dp[i][j]$ ，避免重复。

3. 算法步骤

1. 读取根符号、非终结符集、终结符集。
2. 读取产生式，直到遇到 # -> # ，并分类存储。
3. 对于每个候选字符串：
   • 初始化 $dp$ 表（长度 1）。
   • 按长度递增动态规划填充 $dp$ 表。
   • 判断根符号是否在 $dp[0][n-1]$ 中，输出结果。
4. 每个测试用例后输出一个空行。

---

代码实现

// Right Words
// UVa ID: 10597
// Verdict: Accepted
// Submission Date: 2026-01-30
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

int main() {
    string root;
    while (cin >> root) {
        string V, T;
        cin >> V >> T;

        // 存储产生式
        vector<pair<char, string>> productions;
        string line;
        // 读取产生式，直到遇到 # -> #
        while (getline(cin, line)) {
            if (line == "# -> #") break;
            if (line.empty()) continue;
            // 解析产生式，格式如 "A -> BC" 或 "A -> a"
            char left = line[0];
            string right = line.substr(5);
            productions.push_back({left, right});
        }

        // 预处理：将产生式分类存储
        map<char, vector<string>> toTerminal;   // A -> a
        map<string, vector<char>> toNonTerminal; // A -> BC 映射为 BC -> A

        for (auto& prod : productions) {
            char left = prod.first;
            string right = prod.second;
            if (right.size() == 1) {
                // A -> a
                toTerminal[left].push_back(right);
            } else {
                // A -> BC
                toNonTerminal[right].push_back(left);
            }
        }

        // 处理候选字符串
        string candidate;
        while (getline(cin, candidate)) {
            if (candidate == "#") break;
            if (candidate.empty()) continue;

            int n = candidate.size();
            vector<vector<set<char>>> dp(n, vector<set<char>>(n));

            // 初始化：长度为 1 的子串
            for (int i = 0; i < n; i++) {
                char ch = candidate[i];
                for (char nt : V) {
                    if (toTerminal.count(nt)) {
                        for (string& term : toTerminal[nt]) {
                            if (term[0] == ch) {
                                dp[i][i].insert(nt);
                                break;
                            }
                        }
                    }
                }
            }

            // 动态规划：长度从 2 到 n
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i <= n - len; i++) {
                    int j = i + len - 1;
                    for (int k = i; k < j; k++) {
                        // 检查所有可能的 B 和 C 组合
                        for (char B : dp[i][k]) {
                            for (char C : dp[k + 1][j]) {
                                string bc = string(1, B) + C;
                                if (toNonTerminal.count(bc)) {
                                    for (char A : toNonTerminal[bc]) {
                                        dp[i][j].insert(A);
                                    }
                                }
                            }
                        }
                    }
                }
            }

            // 判断根符号是否在 dp[0][n-1] 中
            if (dp[0][n - 1].count(root[0]))
                cout << candidate << " is in L(G)" << endl;
            else
                cout << candidate << " is not in L(G)" << endl;
        }
        cout << endl;
    }
    return 0;
}