一道关于字符串匹配多正则表达式的问题

是昨天和boss讨论想法的时候遇到的问题，其实不难，但是太久没写干货了就记录一下好了。

问题是这样的，如果有一个字符串 S 和两个正则表达式 P_1 和 P_2 ，问是否存在一种方法可以把 S 拆分成2个子串 s_1 和 s_2 ，使得 s_1 匹配 P_1 ， s_2 匹配 P_2 ， s_1 和 s_2 没有重复使用 S 中的元素，并且它们合并以后恰好得到 S ？如果可以的话，输出 s_1 和 s_2 。

比方说

S = aabcdcdc

P_1 = aac*

P_2 = bd*

那么可以把 S 拆成

s_1 = aaccc

s_2 = bdd

aaccc 可以匹配 aac* ， bdd 可以匹配 bd* ，合并以后恰好是 aabcdcdc

解法是比较经典的用一个合并状态机跟踪两个状态机的状态的方法，既把两个正则表达式先转换成等价的NFA，然后建立一个新NFA，它的状态集合是原本2个NFA状态集合的笛卡尔积，这样我们就知道匹配到字符串的某一位时两个状态机分别在什么状态了。

因为每次转移状态要把当前的输入字母分配给其中一个NFA，在连状态之间的边的时候需要特殊考虑。在原本的任意一个NFA中，如果状态 st_1 可以转移到状态 st_2 ，那么在新状态机中，对于任意的状态 (st_1, st') 和 (st_2, st') ，应当能从前者转移到后者，边上的字母和原NFA里是一样的，但是这里另一个NFA里的状态 st' 必须是同一个，这样每读入一个字母可以保证只有一个NFA的状态会转变，也就是说，这个字母只被分配给了一个NFA。

对于每一个输入字母，这个新NFA会非确定地尝试把它分别分配给原来的两个NFA之一，因为NFA本来就是非确定的，所以这没有引入额外时间复杂度。最后当两个NFA都到达接受态的时候，才能认为这个新状态机到达了接受态，也就是 (fin, fin) 是唯一一个接受态。只要处理完最后一个字符后 (fin, fin) 是一个可能的激活态，这个分配就是可能的。只要在每一步记录下转移的过程，最后追溯一下，就能把字符串具体怎么分求出来了。

因为NFA匹配一个字符串的时间复杂度是NFA大小乘以字符串长度，这个算法的总复杂度是 O(|S| |P_1| |P_2|) ，这里两道竖线表示大小。

当然，这个问题还可以有更高难度的版本，比如有很多条正则表达式怎么办？比如有些字母可以没有用怎么办？比如这里的模型不是正则表达式而是一些更复杂的东西怎么办？用类似的方法大约都是可以解决的。