给孩子起名 The Best Name for Your Baby
题意翻译
给一个包含$n$条规则的上下文无关文法和长度$l$($1\le n \le 50$ , $0\le l \le 20$),求出满足该文法的串中,长度恰好为$l$的字典序最小串。如果不存在,输出单个字符“-”。
“满足文法”是指可以不断使用规则,把单个大写字母S变成这个串。每条规则形如A→a,其中A是一个大写字母(表示非终结符),a是一个由小写字母组成的字符串(长度不超过10,且可以为空串)。该规则的含义是可以用字符串a来替换当前字符串中的大写字母A(如果有多个A,每次只替换一个)。
例如,有四条规则:S→aAB,A→空串,A→Aa,B→AbbA,那么aabb满足该文法,因为S→aAB(规则1)→aB(规则2)→aAbbA(规则4)→aAabbA(规则3)→aAabb(规则2)→aabb(规则2)
翻译自 刘汝佳 《算法竞赛入门经典(第二版)》
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4121
[PDF](https://uva.onlinejudge.org/external/13/p1375.pdf)