正則表達式填字遊戲

以下Find string to regular expression programmatically?，我們假設需要線性時間才能找到匹配正則表達式的字符串。我的表示說我們也可以編程的方式解決一個正則表達式的填字遊戲，對嗎？正則表達式填字遊戲

如果是，解決NxM正則表達式填字遊戲的時間複雜度是多少？

例子：

來源

2017-09-18 gsamaras

這是NP難，即使你禁止反向引用。從exact set cover problem到這個問題有一個簡單的映射。

如果你有套S[1], S[2], ..., S[n]（與工會S），並且不失一般性，該集包含所有的數字1 ... N一些N.代表的S[i]爲長度爲N的字符串，在1如果k在S[i]中則爲第k個地方，否則爲0。讓您的正則表達式拼圖的列全部相同 - 0*10*，並且第k行是「（S [k]）|（0 *）」。

例如，如果S[1] = {1, 4}, S[2] = {2}, S[3] = {3}，和S[4] = {2, 3}，然後難題是：

  0*10* 0*10* 0*10* 0*10* 
1001|0* 
0100|0* 
0010|0* 
0110|0*

對此的解決方案的regexp難題是{1，2，3，4}與S[i]一個確切的蓋。

來源

2017-09-20 07:22:46

「即使您不允許反向引用。」你什麼意思？ – gsamaras

你在這個問題中的例子有'\ 1'和'\ 2'，它們不是正則表達式的一部分，雖然有些實現允許它們。通常，確定帶有反向引用的正則表達式是否匹配字符串需要指數時間。 –

正則表達式填字遊戲

回答

相關問題