UVA1672 不相交的正规表达式 Disjoint Regular Expressions

Mark正在为"火卫一"和"火卫二"的居民开发一个新的社交网络Facepalm.他最近的任务是在每一个帐户中添加关于家乡小行星的信息。当然，每个帐户所有者都可以输入这样的信息，但是Mark决定，如果在登录时给用户填上一些默认值，会更方便一些。 她对这一情况进行了调查，并且她发现用户的姓氏可以从她们家乡的小行星来分析到。Facepalm的每个用户的姓氏是一个非空单词，由英文字母的小写字母组成。 Facepalm用户的姓氏与正则表达式P匹配，而Deimos用户的姓氏与表达式D匹配。然而，问题是有些姓氏可以同时匹配这两个表达式。如果没有匹配两个表达式的非空字符串S，则认为两个表达式不相交。 Mark认为P和D的是不相交的。但是她需要你的帮助来检查它。您将得到两个正则表达式P和D。检查它们是否不相交，如果相交，则查找匹配它们的最短的非空字符串。如果有多个个最短的公共字符串，您找到任何一个都是可以的。 注意：让我们开始正式定义正则表达式和匹配字符串。 - 这一个小写字母c是一个正则表达式，它只匹配一个由单个字母c组成的字符串。 - 交替:如果正则表达式P和Q,那么(P | Q)是一个正则表达式字符串α,如果α匹配P 或者是 α匹配 Q，那么就匹配。 - 级联：如果P和Q是正则表达式，那么（P Q）是一个正则表达式字符串α， 如果 α=βγ并且 β匹配P，γ匹配Q，那么就匹配。 - kleene ：如果P和Q是正则表达式，那么（P）是一个正则表达式字符串α，如果α可以表示为零个或多个字符串的串联α1α2。…，那么αk与所有与αi匹配的空字符串都与Kleene 匹配。 在括号省略这种情况下，Kleene具有最高的优先级，然后是级联，然后是交替。例如在这种情下，""表示""。

无

无