生成正则表达式以匹配列表 A 中的字符串，但不匹配列表 B 中的字符串

Question

可能的重复：
如何从给定的字符串列表自动生成正则表达式？

我有两个字符串列表ListA和ListB。我需要生成一个正则表达式，该表达式将匹配ListA中的所有字符串，并且不匹配ListB中的任何字符串。

• 字符串可以包含字符、数字和标点符号的任意组合。
• 如果字符串出现在ListA 上，则保证它不会出现在ListB 中。
• 如果一个字符串不在这两个列表中的任何一个中，我不在乎匹配的结果应该是什么。

列表通常包含数千个字符串，并且字符串彼此非常相似。

我知道这个问题的微不足道的答案，它只是生成一个正则表达式，形式为(Str1)|(Str2)|(Str3)where StrNis the string from ListA. 但我正在寻找一种更有效的方法来做到这一点。

理想的解决方案是某种工具，它将采用两个列表并为此生成一个 Java 正则表达式。

更新 1：通过“高效”，我的意思是生成比平凡解决方案更短的表达式。理想的算法将生成可能的短路表达式。这里有些例子。

ListA = { C10 , C15, C195 }
ListB = { Bob, Billy }

理想的表达是

/^C1.+$/

再举一个例子，注意ListB的第三个元素

ListA = { C10 , C15, C195 }
ListB = { Bob, Billy, C25 }

理想的表达是

/^C[^2]{1}.+$/

最后一个例子

ListA = { A , D ,E , F , H } ListB = { B , C , G , I }

理想的表达式与平凡的解决方案相同，即

/^(A|D|E|F|H)$/

此外，我不是在寻找理想的解决方案，任何比平凡更好的方法都会有所帮助。我正在考虑生成简单解决方案列表，然后尝试合并公共子字符串，同时观察我们不会徘徊在 ListB 领域。

**更新 2*：我并不特别担心生成 RegEx 所需的时间，在现代机器上任何低于 10 分钟的时间都是可以接受的

Answer 1

如果保证两个列表中都没有字符串，并且你不关心两个列表中都不存在的字符串，那么你只需要匹配ListA中的字符串即可；你可以完全忽略ListB。

您提到的“简单答案”是一个完全合理的解决方案。当您说您想要一种“更有效”的方法时，您是指一种生成正则表达式本身的有效方法，还是一种生成更有效地匹配字符串的正则表达式的方法？

• 如果您想有效地生成正则表达式，大多数语言的字符串工具都提供了一种将字符串列表与分隔符字符串（例如逗号）连接起来以生成单个字符串的方法。没有比这更高效的方法了。
• 如果您希望表达式能够有效地匹配内容，请确保在使用它之前“编译”它。（大多数正则表达式库都有此功能。）编译正则表达式意味着生成正则表达式库实际用于匹配操作的有限状态机。任何像样的正则表达式库都应该在优化 FSM 方面做得很好，例如在可能的情况下将公共子字符串映射到相同的 FSM 状态。

或者，您可以完全放弃正则表达式，而只迭代 ListA 并将其每个字符串与候选字符串进行比较。在这种情况下，单独比较可能会更快，因为查找精确的字符串匹配可以比较 4 或 8 字节块中的字符串，而正则表达式必须单独查看每个字符。但是，如果您有很多字符串要比较，您将在内存中多次遍历候选字符串。相反，正则表达式可以遍历候选字符串一次以查找是否匹配。

尝试这两种方法。看看哪个更快。