程序员面试宝典-一个字符串中连续出现次数最多的子串-CSDN博客

本文链接：https://blog.csdn.net/wwlcsdn000/article/details/79284118

本文探讨了程序员面试中的一道题——找出一个字符串中连续出现次数最多的子串。介绍了暴力解法，通过逐个子串扫描记录每个子串的出现次数，并利用后缀数组的特性来寻找连续子串。对于字符串'abababc'，解法得出连续出现三次的子串'ab'。

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

程序员面试宝典-一个字符串中连续出现次数最多的子串

一个字符串中连续出现次数最多的子串

题目

题目：求一个字符串中连续出现次数最多的子串，请给出分析和代码。
这里首先要搞清楚子串的概念， 1个字符当然也算字串，注意看题目，是求连续
出现次数最多的子串。如果字符串是abcbcbcabc，这个连续出现次数最多的子串是bc，连续
出现次数为3次。如果类似于abcccabc，则连续出现次数最多的子串为c，次数也是3次。

暴力的解法

这个题目可以首先逐个子串扫描来记录每个子串出现的次数。
比如：例如字符串“abababc”,最多连续出现的为ab，连续出现三次。
解决这个问题我们用到了后缀数组这个数据结构。
求一个字符串中连续出现的次数最多的子串，首先生成后缀数组例如上面的字符串为:
1.abababc
2.bababc
3.ababc
4.babc
5.abc
6.bc
7.c
可以看出第一个后缀数组和第三个后缀数组的起始都为ab，第5个后缀数组也为ab。
可以看出规律来，一个字符串s，如果第一次出现在后缀数组i的前面，那么如果它重复出现,
下一次出现应该在第i+len(s)个后缀数组的前面。
这个规律也不难看出。
如果要满足子串连续我们要考虑
比如第一个和第二个字符的前一个字符比较
比如第一个和第三个字符的前两个字符比较
比如第一个和第四个字符的前三个字符比较
比如第一个和第五个字符的前四个字符比较
这里写图片描述
那么从头到尾按照这个规律搜索下不难得出结果。