1

我正在为用户构建一个小型过滤器实用程序来快速过滤项目列表，并且我想按顺序匹配单词的开头，最好使用正则表达式：

考虑一个用户试图找到标记为 的项目here is some text。

  • 我已经知道如何让它匹配任何一个单词的开头：

她——她的e 是一些文本——\bher
所以——这是我的文本——\bso
分机——不匹配——\bext

  • 而且我知道如何使它匹配几个单词的第一个字母：

hist -这是一些文本- ht -这是一些文本- _ _\bh.*?\bi.*?\bs.*?\bt
\bh.*?\bt

  • 我需要的是能够匹配n几个单词的第一个字符：

herst — her e is some t ext iso — here is so me text teh —不匹配

我这样做是因为我的项目通常包含 intialisms，并且用户可能会键入usc以尝试快速拉出US A、C alifornia

我正在为每个输入重写模式，所以我可以做一些工作，这在案例 #2 中是必要的。我正在寻找一种解决方案，无论是模式复杂度还是总复杂度，都可以随字符数线性扩展。

鉴于这些限制，匹配这些字符串的最佳选择是什么？

4

4 回答 4

2

我认为这对于标准的正则表达式库是不可行的。

但是鉴于您的限制，您应该能够编写自己的解析器来进行匹配。保留一堆模式，然后从头到尾扫描输入文本。您需要跟踪的唯一状态是前一个字符是边界还是从堆栈中取出项目。如果您在没有清空堆栈的情况下到达输入末尾，则不匹配。

在伪代码中：

pattern = "herst"
input = "here is some text"
state = true
until input.empty? or pattern.empty? do
  if input[0] == pattern[0] and state
    pattern.shift!
  else
    state = is_boundary(input[0])
  endif
  input.shift!
done
return pattern.empty?
于 2012-06-11T20:55:44.593 回答
1

像这样的怪物：

 \bh(.*?\b)?e(.*?\b)?r(.*?\b)?s(.*?\b)?t

本质上，每个字母要么在前一个字母之前，要么是一个以单词边界结尾的随机序列(.*?\b)。所以，我们使这个随机序列 + \b 可选?。(.*?\b)?因此，在所有字母之间分解它应该有效。

于 2012-06-11T20:56:21.490 回答
0

使用纯正则表达式以灵活的方式做到这一点是很困难的，如果不是不可能的话。我想到的一种可能的方法是首先尝试使用单词边界进行简单的正则表达式匹配，就像您已经完成的那样，然后生成一组所有可能的前缀和后缀对并与它们进行匹配。但是，如果您希望能够匹配字符串中任意两个以上的单独单词，您可能应该编写一个简单的函数来遍历正在搜索的字符串，尝试匹配查询字符串中的最长前缀。一旦找到最长的前缀，就继续搜索字符串中的下一个单词，并尝试匹配查询的其余部分（即减去已经匹配的前缀），并继续这样做直到整个查询已匹配，或搜索到的字符串结束。这应该很容易递归地实现。

于 2012-06-11T21:04:00.540 回答
-2

尝试使用^<myregex>字符串的开头和<myregex>$结尾。

于 2012-06-11T20:52:47.673 回答