Home => ProblemSet => 300-22:正则表达式
1419: 300-22:正则表达式
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
按照如下方式定义正则表达式：
Input
输入第一行包含一个正整数 m ，表示游戏的参数。
输入第二行包含一个非空字符串 r，表示 Alice 选择的正则表达式。
输入第二行包含一个非空字符串 r，表示 Alice 选择的正则表达式。
Output
输出一行一个整数，表示 k 的最小值。
Sample Input Copy
2
(a|b)
Sample Output Copy
1
HINT
样例一解释：
这个时候，Alice 需要判断 s 是否为空，因此可以询问空串
样例二解释：
这个时候 Alice 可以询问 a*
样例三：
输入：
输出：
2
解释：
这个时候，Alice 的一个最优方案是询问 a 和 ab。
样例四：
输入：
输出：
2
这个时候，Alice 的一个最优方案是询问 ((a)*|(d)*) 和 ((b)*|(c)*)
样例五：
输入：
输出：
3
这个时候，Alice 需要判断 s 是否为空，因此可以询问空串
样例二解释：
这个时候 Alice 可以询问 a*
样例三：
输入：
2
a(a|bb)
输出：
2
解释：
这个时候，Alice 的一个最优方案是询问 a 和 ab。
样例四：
输入：
2
(((a)*b|(b)*a)|((c)*a|(d)*b))
输出：
2
这个时候，Alice 的一个最优方案是询问 ((a)*|(d)*) 和 ((b)*|(c)*)
样例五：
输入：
6
f(ca|f)e((((((abfe)*)*)*(b|c)fdfb)*|(bced|(bdab)*(be|da))))*
输出：
3