【HDOJ】2459 Maximum repetition substring-白红宇

【HDOJ】2459 Maximum repetition substring

阅读量：7091 次

发布时间：2019-06-28

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

后缀数组+RMQ。

1 /* 2459 */  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
          6 #include 
         
            7 #include 
          
            8 #include 
           
             9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
               
                 13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 #include 
                   
                     17 #include 
                    
                      18 #include 
                     
                       19 #include 
                      
                        20 #include 
                       
                         21 #include 
                        
                          22 using namespace std; 23 //#pragma comment(linker,"/STACK:102400000,1024000") 24 25 #define sti set
                         
                           26 #define stpii set
                          
                           
                             > 27 #define mpii map
                            
                              28 #define vi vector
                             
                               29 #define pii pair
                              
                                30 #define vpii vector
                               
                                
                                  > 31 #define rep(i, a, n) for (int i=a;i
                                 
                                  =a;--i) 33 #define clr clear 34 #define pb push_back 35 #define mp make_pair 36 #define fir first 37 #define sec second 38 #define all(x) (x).begin(),(x).end() 39 #define SZ(x) ((int)(x).size()) 40 #define lson l, mid, rt<<1 41 #define rson mid+1, r, rt<<1|1 42 43 const int INF = 0x3f3f3f3f; 44 const int maxn = 1e5+5; 45 char s[maxn]; 46 int a[maxn]; 47 int rrank[maxn], height[maxn], sa[maxn]; 48 int wa[maxn], wb[maxn], wc[maxn], wv[maxn]; 49 int dp[maxn][17]; 50 int mx[maxn], L[maxn]; 51 52 bool cmp(int *r, int a, int b, int l) { 53 return r[a]==r[b] && r[a+l]==r[b+l]; 54 } 55 56 void da(int *r, int *sa, int n, int m) { 57 int i, j, *x=wa, *y=wb, *t, p; 58 59 for (i=0; i
                                  
                                   =0; --i) sa[--wc[x[i]]] = i; 63 for (j=1,p=1; p
                                   
                                    = j) y[p++] = sa[i] - j; 66 for (i=0; i
                                    
                                     =0; --i) sa[--wc[wv[i]]] = y[i]; 71 for (t=x, x=y, y=t, p=1, i=1, x[sa[0]]=0; i
                                     
                                       r) 97 swap(l, r); 98 99 int k = 0;100 ++l;101 while (1<<(k+1) <= r-l+1)102 ++k;103 104 return min(dp[l][k], dp[r-(1<
                                      
                                       > 1, tmp;136 rep(i, 1, n_) {137 mx[i] = 0;138 for (int p=0, q=i; q
                                       
                                        = n)165 continue;166 167 tmp = RMQ(rrank[p], rrank[p+L[j]]);168 if (tmp/L[j]+1 >= ans) {169 beg = p;170 len = L[j] * ans;171 goto _output;172 }173 }174 }175 176 _output:177 s[beg+len] = '\0';178 puts(s+beg);179 }180 181 int main() {182 ios::sync_with_stdio(false);183 #ifndef ONLINE_JUDGE184 freopen("data.in", "r", stdin);185 freopen("data.out", "w", stdout);186 #endif187 188 int t = 0;189 190 while (scanf("%s", s)!=EOF && (s[0]!='#')) {191 printf("Case %d: ", ++t);192 solve();193 }194 195 #ifndef ONLINE_JUDGE196 printf("time = %d.\n", (int)clock());197 #endif198 199 return 0;200 }

数据生成器。

1 from random import randint, shuffle 2 import shutil 3 import string 4  5  6 def GenDataIn(): 7     with open("data.in", "w") as fout: 8         t = 20 9         bound = 10**210         lc = list(string.lowercase)11         for tt in xrange(t):12             length = randint(100, 500)13             line = ""14             for i in xrange(length):15                 idx = randint(0, 25)16                 line += lc[idx]17             fout.write("%s\n" % line)18         fout.write("#\n")19         20                 21 def MovDataIn():22     desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"23     shutil.copyfile("data.in", desFileName)24 25     26 if __name__ == "__main__":27     GenDataIn()28     MovDataIn()

转载于:https://www.cnblogs.com/bombe1013/p/5179447.html

你可能感兴趣的文章

MySQL主从介绍、准备工作、配置主、配置从、测试主从同步