编程珠玑---读书笔记---使用后缀数组查找最长重复子串-白红宇

编程珠玑---读书笔记---使用后缀数组查找最长重复子串

阅读量：6153 次

发布时间：2019-06-21

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

后缀数组是一个字符指针数组，数组中指针所指的对象包含了字符串的每一个后缀，因此成为后缀数组。

看代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define MAXN 5000000char c[MAXN],*a[MAXN];bool cmp(char *p,char *q) //对后缀数组进行排序所用的谓词函数 { return strcmp(p,q)<0;}int comlen(char *p,char *q) //计算最长公共子串的长度 { int i=0; while(*p && (*p++==*q++))i++; return i;}int main(){ char ch; int n=0; while((ch=getchar())!=EOF) { c[n]=ch; a[n]=&c[n]; n++; } c[n]='\0'; sort(a,a+n,cmp); //for(int i=0;i
                
                 <
                 
                  <
                  
                   maxlen){ maxlen=comlen(a[i],a[i+1]); maxi=i; } } printf("%.*s\n",maxlen,a[maxi]); //输出前maxlen个字符 return 0;}