后缀数组求字符串最长重复子串-白红宇

后缀数组求字符串最长重复子串

阅读量：4653 次

发布时间：2019-06-09

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

求一个字符串的最长重复子串：

1.求字符串s的后缀数组suffix

2.suffix排序

3.求最长公共前缀

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;int comlen(string s1,string s2){ //计算两个字符串的最长公共前缀 int i=0,j=0; int len=0; while(i
                 
                  
                    suffix; //后缀数组 string ans; int len=0; int maxlen=0; int i; for(i=0;i
                   
                    maxlen) { maxlen=len; ans=suffix[i].substr(0,maxlen); } } return ans;}int main(){ string str; while(cin>>str) { if(str=="") cout<<""<