当前位置 博文首页 > 可惜浅灰的博客：改版KMP算法：洛谷P3375 KMP字符串匹配
题目描述：
给出两个字符串?s1??和?s2?，若?s1??的区间?[l,r]?子串与?s2??完全相同，则称?s2??在?s1??中出现了，其出现位置为?l。
现在请你求出?s2??在?s1??中所有出现的位置。
定义一个字符串?s?的 border 为?s?的一个非s本身的子串?t，满足?t?既是?s?的前缀，又是?s?的后缀。
对于?s2?，你还需要求出对于其每个前缀?s′?的最长 border?t′?的长度。
输入：?第一行为一个字符串，即为?s1?；第二行为一个字符串，即为?s2?。
输出：首先输出若干行，每行一个整数，按照从大到小顺序出?s_2s2??在?s_1s1??中出现的位置。
最后一行输出?∣s2?∣?个整数，第?i?个整数表示?s2??的长度为?i?的前缀的最长 border 长度。
解题思路：
? ? 1、属于模式匹配KMP算法，整体思想与《算法导论》上的KMP算法一致，但是细节不同，本题中用下标描述，《算法导论》中用的是自然序，所以要改变求解next序列的函数；而且要求出所有的匹配成功子序列，不是第一个子序列。
? ? 2、求解next序列时，把所有的参数初始值都-1，再改变while循环中的上界，确保不会出界即可；
? ? 3、在匹配函数中，遍历s1和s2均按照下标进行，初始值为0；其余不变，匹配成功都+1，不成功j回退；
? ? 4、在匹配while循环外再设置一层while循环，在匹配成功一次后，令j = go_back[j]，即可实现依次输出所有匹配成功的串的首元素下标。
代码实现：
? ??
#include <iostream>
using namespace std;
#include <string>
int go_back[100 + 5];
void GetGoBack(const string& s)
{
int i = 0, k = -1;
int len = s.size();
go_back[0] = -1;
while (i < len)
{
if (k == -1 || s[i] == s[k])
{
go_back[++i] = ++k;
}
else
{
k = go_back[k];
}
}
}
void KMP(const string& s1, const string& s2)
{
int i = 0, j = 0;
int len1 = s1.size();
int len2 = s2.size();
while (i < len1)
{
while (i < len1 && j < len2)
{
if (j == -1 || s1[i] == s2[j])
{
i++;
j++;
}
else
{
j = go_back[j];
}
}
if (j == len2)
{
cout << i - len2 + 1 << endl;
j = go_back[j];
}
}
}
int main()
{
string s1, s2;
cin >> s1 >> s2;
GetGoBack(s2);
KMP(s1, s2);
int len = s2.size();
for (int i = 1; i <= len; i++)
{
cout << go_back[i] << " ";
}
cout << endl;
return 0;
}