找出全部最长连续反复子串及其个数-白红宇

找出全部最长连续反复子串及其个数

阅读量：5280 次

发布时间：2019-06-14

本文共 1319 字，大约阅读时间需要 4 分钟。

问题描写叙述：

找出字符串中所以最长连续反复子串及其个数

比方：输入：123234，最大连续反复字符串为23，个数为2

输入：5555，最大连续反复字符串为555，个数为2

输入：aaabbb 最大连续反复字符串为aa，个数为2；和bb，个数为2

必须存在反复的字符串才算，仅仅出现一次的不算。可能存在多个同样长度的不同字符串，比方aaabbb。

分析：最直接的想法是利用两个指针循环遍历比較全部可能的子串，记录下全部子串长度，然后找到全部最大连续子串及其个数。时间复杂度为O(n^2)。

在网上看到一种利用后缀树组的方式来处理的方法，其思想主要是将字符串的全部后缀子串用数组记录下来，然后将全部子串按字典序排序，然后依次比較相邻的字符串就可以统计出全部可能的连续反复子串，降低了非常多不必要的比較。时间复杂度主要是字符串排序的复杂度，为O(nlogn)。主要代码例如以下：

#include
       
        #include
        
         #include
         #include
          
           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
           
             chmap;	int i,n,max=0;	cin>>s;	n=strlen(s);	if(n==0)		return 0;	for(i=0;i
            
             ::iterator it=chmap.find(subs); if(it!=chmap.end()) { it->second++; } else chmap.insert(make_pair(subs,2)); } cout<<"Result:"<
             
              ::iterator i=chmap.begin();i!=chmap.end();i++) cout<
              
               first<<" "<
               
                second<
                
                 ::iterator i=chmap.begin();i!=chmap.end();i++) delete i->first; return 0;}

转载于:https://www.cnblogs.com/llguanli/p/8706992.html

你可能感兴趣的文章