我认为这个问题与使用有限状态计算模型匹配字符串的想法有关。
可以通过使用KMP字符串匹配算法来解决此问题。
KMP算法尝试在文本字符串中查找模式字符串的匹配项,考虑到即使在某些点上发现不匹配,仍然匹配了多少前缀。
为了确定“如果我们在匹配到模式索引i之后遇到不匹配,还能匹配多少前缀”,需要提前构建一个失败函数。(请参考下面的代码以获取构建失败函数值的方法)
对于每个模式索引i,该失败函数将告诉我们,即使在索引i之后遇到不匹配,模式的多少前缀仍然可以匹配。
思路是找出模式的最长合适前缀的长度,该前缀也是其每个子字符串(由1到i索引表示,其中i从1到n)的后缀。
我使用字符串索引从1开始。
因此,任何模式的第一个字符的失败函数值为0。(即到目前为止没有匹配任何字符)。
对于后续字符,对于每个索引i = 2到n,我们看一下pattern[1...i]子串的最长合适前缀是该子串的哪个后缀。
假设我们的模式是"aac",则索引1的失配函数值为0(尚未匹配),索引2的失配函数值为1(与“aa”的最长合适前缀相同的最长合适后缀长度为1)
对于模式"ababac",索引1的失配函数值为0,
索引2的失配函数值为0,索引3的失配函数值为1(因为第三个索引'a'与第一个索引'a'相同),索引4的失配函数值为2(因为在索引1和2处的“ab”与在索引3和4处的“ab”相同),而索引5的失配函数值为3(在索引[1...3]处的“aba”与在索引[3...5]处的“aba”相同)。对于索引6,失配函数值为0。
以下是构建失配函数并使用它匹配文本(或流)的代码(C++):
int s = 1;
int t = 0;
int *f = new int[n+1];
f[1] = 0;
for (s = 1; s < n; s++) {
while (t > 0 && pattern[t + 1] != pattern[s + 1]) {
t = f[t];
}
if (pattern[t + 1] == pattern[s + 1]) {
t++;
f[s + 1] = t;
}
else {
f[s + 1] = 0;
}
}
int count = 0;
char current_char = stream.next_char();
s = 0;
while (current_char != '\0') {
while (s > 0 && current_char != pattern[s + 1]) {
s = f[s];
}
if (current_char == pattern[s + 1]) s++;
if (s == n) {
count++;
}
current_char = stream.next_char();
}
printf("Count is %d\n", count);
`
注意:此方法可帮助查找重叠模式出现的计数。例如,在流“ababa”中,单词“aba”出现了两次。
lengthOfTheWord
个字符,并在每次调用next_char()
后进行完整的字符串比较。更好答案的提示:是否有子字符串搜索算法只检查文本中递增顺序的字符,而不跳过某些字符? - j_random_hacker