相关疑难解决方法(0)

我知道我可以通过一系列for循环遍历字符串来实现这一点,但那将是糟糕的编程.好吧,我的教授更喜欢我不这样做.我想使用正则表达式来做到这一点.

我在任何地方都没有得到答案.正则表达式匹配和替换的运行时复杂性是多少？

编辑:我在python中工作.但是想知道大多数流行的语言/工具(java,perl,sed).

我想匹配任何开始/结束或不包含单词“end”但忽略单词“end”的单词，例如：

• 你好 - 会匹配
• 男朋友 - 会匹配
• 无穷无尽 - 匹配
• endend - 匹配

但

• 结束 -不匹配

我正在使用，^(?!end)).*$但它不是我想要的。

对不起我的英语不好

我正在使用grep在单个文件中搜索几个正则表达式.特别是,我正在考虑一个带有英文字幕的100 MB文件, 并运行存储在文件patterns.txt中的以下正则表达式:

Cas.*eharden
acr.*otic
syn.*thesizing
sub.*abbot
iss.*acharite
bot.*onne
dis.*similatory
ove.*rmantel
isa.*tin
ado.*nijah
sol.*ution
zei.*st
fam.*ousness
inq.*uisitress
aor.*tography
via.*duct
ama.*sa
der.*ive
pie.*tas
kit.*chenette

在这样做时,我观察到grep所需的时间不会与正则表达式的数量呈线性增长.实际上,它似乎呈指数级增长.

实验

系统: Intel(R)Core(TM)i5-5200U CPU @ 2.20GHz; 4个核心; 8 GB RAM

案例1:20 regexps

命令grep -c -f patterns.txt subtitles.txt计数2214次并且需要
2,19s用户0,00s系统99%cpu 2,192总计.

案例2:30 regexps

如果我将以下表达式添加到patterns.txt

ort.*hros
ove.*ridentify
mis.*tiest
pay.*ne
int.*erchasing
jej.*uneness
sta.*lactiform
und.*ertrain
cob.*bles
Sub.*category

命令grep -c -f patterns.txt subtitles.txt计数2894次并占用71,35s用户0,06s系统99%cpu 1:11,42总计.

案例3:35个正则表达式

再添加五个表达式:

dis.*embosom
imp.*ortunateness
ema.*thion
rho.*mb
haz.*elwood

命令 …

如果我有一个大约3000个字符的文本.我想搜索具有某些特征的字符串,例如字符串[*].

也就是说,我想[a]和[bc]来自

sjfhshdkfjhskdhfksdf[a]sfdsgfsdf[bc]

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

我怎么能比O(n ^ 2)更好地做到这一点？如果我使用java,是否有任何光库？

可以检测字符串中重复单词的方法是什么？

例如"这是重复测试的测试消息"包含一个重复的单词测试.

这里,目标是检测String中出现的所有重复单词.

使用正则表达式对于实现目标是优选的.