字符串的匹配
就像多数的计算机问题一样,字符串匹配的描述是极其易懂的。
给定两个字符串key和target
寻找所有的整数s满足\forall{i}\in\lbrace x \mid x \in N, 0 \leq x
朴素字符串匹配
很容易想到对于每一个s
vector<int check(const string& key,const string& target)
{
vector<int ans;
for(int s = 0;s<target.length() - key.length();s++)
{
for(int i = 0;i<key.length();i++)
{
if(key[i]==target[s+i])
{
if(i==key.length()-1)
{
ans.push_back(s);
}
}
else
{
break;
}
}
}
return ans;
}
复杂度是O(key.length()*target.length())
当key和target比较小的时候,这样子当然没有什么问题
但是如果有一天,你需要在一个256MB的文本文件中寻找一个长为1000的字符串
比如在10^9以内的素数表中查找有没有出现\pi的前一千位。这个算法就会消耗好几分钟的时间才能得到结果。
KMP字符串匹配
为了更快地匹配大量字符串(也可以是好多数字或者二进制码)需要找到一种节省时间的方法。
考虑以下情况:
- 对于某个s,我们已经匹配了其后的i-1个字符,但是第i个不能配对,我们称这是一次失败的配对
但是这样的失败是有价值的,让我们知道target中s开始的i-1个字符是匹配的
匹配失败后直接i = 0;
然后s++;
的方法直接抛弃了这样的信息- 假设key中所有字符各不相同,一次匹配失败就能让我们知道
key[0]\notin target[s+1:s+i]
因此可以s += i;i = 0;
然后开始下一轮匹配 - 假设key[0:2]==key[i-2:i]
尽管匹配失败了,但是知道了target[s+i-2:s+i]==key[i-2:i]
那么也就知道了target[s+i-2:s+i]==key[0:2]
这样子,我们可以i = 2;
然后继续尝试匹配
- 假设key中所有字符各不相同,一次匹配失败就能让我们知道
所以,要是能事先对于所有的i计算出最大的k使得key[0:k]==key[i-k:i]
就可以在O(target.length())的时间内完成匹配岂不美哉
确实,可以花费O(key.length())的时间内求得这个数组
让我们称之为next,因为它指示了每次匹配失败时下一步应当匹配哪个字符.
方法其实是对于部分的key使用部分的next
vector<size_t>& caculateNext(const string& key, vector<size_t>& next)
{
//vector<int next;
next.clear();
next.resize(key.length());
next[0] = 0;
size_t j = 0;
for (size_t i = 1; i < key.length(); i++)
{
while (j!=0&&key[j]!=key[i])
{
j = next[j];
}
if (key[j]==key[i])
{
++j;
}
next[i] = j;
}
return next;
}
- 假设next[i]=j,next[j]=k
有key[0:j]==key[i-j+1:i+1]又有key[0:k]==key[j-k+1:j+1]
故有key[0:k]==key[i-k+1:i+1] -
假设j=next[i-1]且k=next[j]
即key[0:j]==key[i-j:i]- 如果key[i]==key[j]
有key[0:j+1]==key[i-j+1:i+1]
next[i]=j+1 - 否则
有key[0:k]=key[i-k:i]
相当于k=next[i-1]
再做上面的判断
- 如果key[i]==key[j]
求出next后应用以下代码
vector<size_t> KMP_string_matcher(const string& target, const string& key, const vector<size_t>& next)
{
vector<size_t> ans;
size_t j = 0;
for (size_t i = 0; i < target.length(); i++)
{
while (j != 0 && target[i] != key[j])
{
j = next[j];
}
if (target[i]==key[j])
{
j++;
}
if (j==key.length())
{
ans.push_back(i - j + 1);
j = next[j-1];
}
}
return ans;
}
总的时间消耗为O(key.length()+target.length())
这里好想插个gif