最长重复子串（可重叠）

最新推荐文章于 2022-10-19 20:07:52 发布

shiyang6017

最新推荐文章于 2022-10-19 20:07:52 发布

阅读量458

点赞数

分类专栏：算法数据结构文章标签：字符串匹配 KMP

本文链接：https://blog.csdn.net/shiyang6017/article/details/52687890

版权

算法同时被 2 个专栏收录

62 篇文章

订阅专栏

数据结构

19 篇文章

订阅专栏

本文深入探讨了KMP算法的实现原理，并通过一个具体的C++代码示例展示了如何使用KMP算法解决字符串匹配问题。文章首先介绍了getNextArray函数的作用及其实现细节，随后通过main函数演示了如何利用KMP算法找出字符串中的最长重复子串。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

void getNextArray(vector<int>& next, const string& s) { 
	next.resize(s.size() + 1); // 多加一位
	next[0] = -1;
	int k = -1, i = 0;
	while ( i < s.size()) {
		if (k == -1 || s[i] == s[k] )
			next[++i] = ++k;
		else
			k = next[k];
	}
}
int main() {// 利用KMP算法求解，时间复杂度O（n*n）
	string str = "ask not what your country can do for you,but..";
	vector<int> next;
	int ret = 0;
	for (int i = 0; i < str.size(); ++i){
		getNextArray(next, str.substr(i));
		ret = max(ret, *max_element(next.begin(), next.end()));
	}
	cout << ret << endl;
	return 0;
}