给定可以包含"*"通配符的文本和模式。是否有可以在 O(n) 时间内匹配的算法？

Question

匹配应涵盖整个文本。

为简单起见，文本是字母数字。

该模式不支持转义，仅接受以下通配符：

"*" - 匹配任何字符序列(也为空(

我已经探索了如下所示的朴素实现。我也浏览了维基百科，但我未能找到是否可以实现线性解决方案的明确答案。

在没有线性解决方案的情况下，欢迎最好的替代方案。

谢谢。

bool strmatch(char txt[], char pat[], 
int n, int m) 
{ 
if (m == 0) 
return (n == 0); 
int i = 0, j = 0, index_txt = -1, 
index_pat = -1; 
while (i < n) { 
if (j < m && txt[i] == pat[j]) { 
i++; 
j++; 
} 
else if (j < m && pat[j] == '*') { 
index_txt = i; 
index_pat = j; 
j++; 
} 
else if (index_pat != -1) { 
j = index_pat + 1; 
i = index_txt + 1; 
index_txt++; 
} 
else { 
return false; 
} 
} 
while (j < m && pat[j] == '*') { 
j++; 
} 
if (j == m) { 
return true; 
} 
return false; 
} 

Answer 1

是的，有一个算法。

您的模式是一个字符串列表，用"*"分隔。 算法是这样的：

1. 将第一个模式字符串与文本开头匹配。
2. 在文本中搜索所有其他模式字符串，从上一个匹配项的末尾开始。字符串搜索可以在线性时间内实现，例如使用此算法。
3. 将最后一个模式字符串与文本末尾匹配。

该算法的复杂度为 O(n+m(，其中 n 为文本大小，m 为图案大小。 Python 中的实现如下所示：

def matchpattern(txt, pattern):
if len(pattern) == 0:
return len(txt) == 0;
strings = pattern.split('*')
if len(strings) == 1: # no star found
return txt == pattern
# match the fist piece
if not txt.startswith(strings[0]):
return False;      
# match all except the last substring
pos = len(strings[0])
for s in strings[1:-1]:
pos = txt.find(s, pos)
if (pos == -1):
return False
pos = pos + len(s)
return len(txt) >= pos + len(strings[-1]) and txt.endswith(strings[-1])
def test(txt, pattern):
print(repr(txt), repr(pattern), matchpattern(txt, pattern))
test('one', 'one')
test('x one', 'one')
test('one', '*')
test('one', '*one')
test('x one', '*one')
test('one x', 'one')
test('one x', 'one*')
test('one x two', 'one*two')    
test('one one', 'one*one*one')

输出：

'one' 'one' True
'x one' 'one' False
'one' '*' True
'one' '*one' True
'x one' '*one' True
'one x' 'one' False
'one x' 'one*' True
'one x two' 'one*two' True
'one one' 'one*one*one' False

Answer 2

我认为有一个由"*"字符分隔的字符串列表。文本必须以列表中的第一个字符串开头，并以列表中的最后一个字符串结尾。所有其他字符串必须按顺序出现在文本其余部分的某个位置。检查第一个和最后一个字符串是否存在很容易。在这两者之间，我认为你可以用 https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm(Knuth-Morris-Pratt(线性时间一次搜索一个其他字符串，在找到前一个字符串后搜索每个字符串。