POJ - 3693 Maximum repetition substring (后缀数组)-白红宇

POJ - 3693 Maximum repetition substring (后缀数组)

阅读量：4981 次

发布时间：2019-06-12

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

The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of "ababab" is 3 and "ababa" is 1.

Given a string containing lowercase letters, you are to find a substring of it with maximum repetition number.

Input

The input consists of multiple test cases. Each test case contains exactly one line, which

gives a non-empty string consisting of lowercase letters. The length of the string will not be greater than 100,000.

The last test case is followed by a line containing a '#'.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by the substring of maximum repetition number. If there are multiple substrings of maximum repetition number, print the lexicographically smallest one.

Sample Input

ccabababcdaabbccaa#

Sample Output

Case 1: abababCase 2: aa

题意:

求重复次数最多的连续重复子串所在的子串

思路:

通过这篇博客找出重复次数最多的连续重复子串出现的次数.

然后在后缀数组的前缀里寻找符合条件的子串.因为后缀数组已经按字典序排好序,所以找到后立即退出.

具体详见代码注释:

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define fuck(x) cerr<<#x<<" = "<
                 
                  <
                  
                   =0&&lcp(k,k+i)>=i){ans++;} if(ans==ansx){ if(flag){ ansl.push_back(i); flag = false; } }else if(ans>ansx){ ansx=ans; ansl.clear(); ansl.push_back(i); flag=false; } } } int siz = ansl.size(); bool flag = false; for(int i=1;i<=len;i++){ for(int j=0;j
                   
                    =(ansx-1)*l){ //核心代码,如果sa[i]和sa[i]+l的公共前缀中包含了ansx-1个l, // 说明sa[i]的前缀中已经包含了ansx个l ans = sa[i]; s[ans+ansx*l]=0; flag=true; } } if(flag){ break;} } printf("Case %d: %s\n",cases,s+ans); } return 0;}

View Code

Maximum repetition substring

转载于:https://www.cnblogs.com/ZGQblogs/p/11177025.html

你可能感兴趣的文章