java - 在文本中搜索特殊字符串的最佳方法

Question

如果我有一段大约 3000 个字符的文本。我想搜索具有某些特征的字符串，例如 [*] 之类的字符串。

也就是我想从

中得到 [a]和 [bc]

sjfhshdkfjhskdhfksdf[a]sfdsgfsdf[bc]

我知道有一种称为 KMP 的算法可以保证通过文本进行线性时间搜索操作，但在这里我没有找到固定的字符串，也许我必须在某些地方使用一些正则表达式。

我怎样才能比 O(n^2) 做得更好？如果我使用的是 java，是否有适用于此的任何轻型库？

Answer 1

不需要库，您已经有效地描述了正则表达式的用例!它们针对搜索进行了高度优化，在本例中为 O(n) .

String str = "sjfhshdkfjhskdhfksdf[a]sfdsgfsdf[bc]";
List<String> allMatches = new ArrayList<>();
Matcher m = Pattern.compile("\\[[^\\]]*]").matcher(str);
while (m.find()) {
    allMatches.add(m.group());
}

Regex Demo

如果你有任何疑问并且真的想要一些你可以看到的 O(n)，这里有一个算法:

String str = "sjfhshdkfjhskdhfksdf[a]sfdsgfsdf[bc]";
List<String> allMatches = new ArrayList<>();
for (int i = str.indexOf('['), j; i != -1; i = str.indexOf('[', j + 1)) {
    j = str.indexOf(']', i + 1);
    // if `j` is -1, the brackets are unbalanced. Perhaps throw an Exception?
    allMatches.add(str.substring(i, j + 1));
}