首页 > 代码库 > 找出所有最长连续重复子串及其个数

找出所有最长连续重复子串及其个数

2024-07-13 16:43:50   215人阅读

问题描述：
找出字符串中所以最长连续重复子串及其个数
比如：输入：123234，最大连续重复字符串为23，个数为2
           输入：5555，最大连续重复字符串为555，个数为2
           输入：aaabbb 最大连续重复字符串为aa，个数为2；和bb，个数为2
必须存在重复的字符串才算，只出现一次的不算。可能存在多个相同长度的不同字符串，比如aaabbb。

分析：最直接的想法是利用两个指针循环遍历比较所有可能的子串，记录下所有子串长度，然后找到所有最大连续子串及其个数，时间复杂度为O(n^2)。在网上看到一种利用后缀树组的方式来处理的方法，其思想主要是将字符串的所有后缀子串用数组记录下来，然后将所有子串按字典序排序，然后依次比较相邻的字符串即可统计出所有可能的连续重复子串，减少了很多不必要的比较，时间复杂度主要是字符串排序的复杂度，为O(nlogn)。主要代码如下：
#include<iostream>
#include<string.h>
#include<map>
#include<algorithm>

using namespace std;


struct scmp

{
    bool operator()(const char *s1, const char *s2) const
    {
        return strcmp(s1,s2)<0;
    }
};


int mycmp(const void *p1, const void *p2)
{
	return strcmp(*(char **)p1, *(char **)p2);
}


int comlen(char *p,char *q)
{
	int len=0;
	while(*p&&*q&&*p++==*q++)
		len++;
	return len;
}



int main()
{
	char s[50];
	char *a[51];
	int cnt[50]={0};
	map<char*,int,scmp> chmap;
	int i,n,max=0;
	cin>>s;
	n=strlen(s);
	if(n==0)
		return 0;
	for(i=0;i<n;i++)
		a[i]=&s[i];
	a[n]=0;
	qsort(a,n,sizeof(char *),mycmp);

	for(i=0;i<n-1;i++)
	{
		int temp=comlen(a[i],a[i+1]);
		if(max<temp)
		{
			max=temp;
		}
		cnt[i]=temp;
	}
	for(i=0;i<n;i++)
		if(cnt[i]==max)
		{						
			char *subs=new char[50];
			strncpy(subs,a[i],max);
			subs[max]='\0';
			map<char*,int,scmp>::iterator it=chmap.find(subs);
			if(it!=chmap.end())
			{
				it->second++;
			}
			else
				chmap.insert(make_pair(subs,2));

		}
	cout<<"Result:"<<endl;
	for(map<char*,int,scmp>::iterator i=chmap.begin();i!=chmap.end();i++)
		cout<<i->first<<" "<<i->second<<endl;

	for(map<char*,int,scmp>::iterator i=chmap.begin();i!=chmap.end();i++)
		delete i->first;

	return 0;
}


联系
我们