广义问题“查找给定字符串的模式”更难解决,因为一个字符串可以符合多个模式。例如,
catcatdogcat
符合许多模式。这是一个非详尽的列表:
aaba cat cat dog cat
a catcatdogcat
ab catcat dogcat
abcabcefgabc c a t c a t d o g c a t
ababcab ca t ca t dog ca t
所以我不认为“找到所有模式,然后看看提议的模式是否在其中”的方法会奏效。
这意味着我们可能希望使用建议的模式作为指导来尝试分解字符串,但我也不完全确定它会是什么样子。
在特定情况下,当模式以相同的子字符串开头和结尾(例如 in aaba
)时,我想您可以从字符串的开头和结尾开始,一次使用一个字符,直到获得匹配:
catcatdogcat
CatcatdogcaT
CAtcatdogcAT
CATcatdogCAT <-- Substring "CAT" is a candidate for "a". Check if that pattern matches.
但更一般的情况又更难了。但是,可以采取类似的方法,例如尝试每个字符串以查看它是否符合模式,并进行回溯:
catcatdogcat
Catcatdogcat <-- The string isn't "CCsomethingC", so a != "C"
CAtcatdogcat <-- the string isn't "CACAsomethingCA", so a != "CA"
CATcatdogcat <-- the string is "CATCATsomethingCAT", so a = "CAT" is a candidate.
找到候选对象后,您可以将其从字符串和模式字符串中删除,从而减少与dog
模式进行比较的下一步b
。在伪代码中,
checkpattern(pattern, string) :=
if (pattern has just one letter)
return true
if (pattern has more than one letter, but it's one character repeated)
return whether the string repeats that way
for (each substring from the start of the string of length x=[0..])
does the string match this candidate substring following the pattern?
if (yes)
if (checkpattern(pattern - letter, string - substring))
return true
else
continue
if (no)
continue
return false
我认为那会奏效。显然这个伪代码有很多细节,而且效率不高,但它可以完成工作。