【HDOJ】4080 Stammering Aliens-白红宇

【HDOJ】4080 Stammering Aliens

阅读量：6950 次

发布时间：2019-06-27

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

1. 题目描述

给定一个长为$n \in [1, 4000]$的字符串，求其中长度最长的子串，并且该子串在原串中出现至少$m$次，并求最右起始位置。

2. 基本思路

两种方法：二分+后缀数组，或者二分+哈希。

（1）二分+后缀数组

对子串长度进行二分，若不同后缀的公共前缀超过这个值，则对计数值累加。若计数值超过m，则证明这个公共前缀是有效的，计数过程中同时维护pos（最右边界），从而更新rpos。

（2）二分+哈希

仍然是对长度进行二分，然后枚举其实位置计算该长度的子串的哈希值，排序后，计算，超过m表示是有效的子串，从而更新最右位置。哈希采用LCP哈希。

3. 代码

（1）后缀数组

1 /* 4080 */  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 maxn = 40005; 44 char s[maxn]; 45 int a[maxn]; 46 int height[maxn], sa[maxn], rrank[maxn]; 47 int wa[maxn], wb[maxn], wc[maxn], wv[maxn]; 48 int rpos, m; 49 50 bool cmp(int *r, int a, int b, int l) { 51 return r[a]==r[b] && r[a+l]==r[b+l]; 52 } 53 54 void da(int *r, int *sa, int n, int m) { 55 int i, j, *x=wa, *y=wb, *t, p; 56 57 for (i=0; i
                                  
                                   =0; --i) sa[--wc[x[i]]] = i; 61 for (j=1,p=1; p
                                   
                                    = j) y[p++] = sa[i] - j; 64 for (i=0; i
                                    
                                     =0; --i) sa[--wc[wv[i]]] = y[i]; 69 for (t=x,x=y,y=t,x[sa[0]]=0,p=1,i=1; i
                                     
                                      = bound) {100 pos = max(pos, sa[i]);101 ++cnt;102 } else {103 if (cnt >= m)104 rpos = max(pos, rpos);105 pos = sa[i];106 cnt = 1;107 }108 }109 if (cnt >= m)110 rpos = max(pos, rpos);111 112 return rpos!=-1;113 }114 115 void solve() {116 int n;117 118 for (int i=0; ; ++i) {119 if (s[i] == '\0') {120 n = i;121 break;122 }123 a[i] = s[i] - 'a' + 1;124 }125 a[n] = 0;126 if (m == 1) {127 printf("%d 0\n", n);128 return ;129 }130 131 da(a, sa, n+1, 30);132 calheight(a, sa, n);133 134 int l = 1, r = n, mid;135 int ans = 0, ansp;136 137 while (l <= r) {138 mid = (l + r) >> 1;139 if (judge(mid, n)) {140 ans = mid;141 ansp = rpos;142 l = mid + 1;143 } else {144 r = mid - 1;145 }146 }147 148 if (ans)149 printf("%d %d\n", ans, ansp);150 else151 puts("none");152 }153 154 int main() {155 ios::sync_with_stdio(false);156 #ifndef ONLINE_JUDGE157 freopen("data.in", "r", stdin);158 freopen("data.out", "w", stdout);159 #endif160 161 while (scanf("%d", &m)!=EOF && m) {162 scanf("%s", s);163 solve();164 }165 166 #ifndef ONLINE_JUDGE167 printf("time = %d.\n", (int)clock());168 #endif169 170 return 0;171 }

（2）哈希

1 /* 4080 */  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 #include 
                         
                           23 using namespace std; 24 //#pragma comment(linker,"/STACK:102400000,1024000") 25 26 #define sti set
                          
                            27 #define stpii set
                           
                            
                              > 28 #define mpii map
                             
                               29 #define vi vector
                              
                                30 #define pii pair
                               
                                 31 #define vpii vector
                                
                                 
                                   > 32 #define rep(i, a, n) for (int i=a;i
                                  
                                   =a;--i) 34 #define clr clear 35 #define pb push_back 36 #define mp make_pair 37 #define fir first 38 #define sec second 39 #define all(x) (x).begin(),(x).end() 40 #define SZ(x) ((int)(x).size()) 41 #define lson l, mid, rt<<1 42 #define rson mid+1, r, rt<<1|1 43 44 #define ULL unsigned __int64 45 46 const int MOD = 754283; 47 const int maxn = 40005; 48 ULL H[maxn], base[maxn]; 49 ULL Hash[maxn]; 50 int pos[maxn]; 51 char s[maxn]; 52 int c[26]; 53 int m, len; 54 int rp; 55 56 void init() { 57 base[0] = 1; 58 rep(i, 1, maxn) 59 base[i] = base[i-1] * MOD; 60 } 61 62 bool comp(const int& a, const int& b) { 63 if (Hash[a] == Hash[b]) 64 return a
                                   
                                    = m) 84 rp = max(rp, pos[i-1]); 85 } 86 87 return rp >= 0; 88 } 89 90 void solve() { 91 len = strlen(s) ; 92 93 memset(c, 0, sizeof(c)); 94 rep(i, 0, len) 95 ++c[s[i]-'a']; 96 H[len] = 0; 97 per(i, 0, len) 98 H[i] = H[i+1] * MOD + s[i]-'a'; 99 100 bool flag = false;101 102 rep(i, 0, 26) {103 if (c[i] >= m) {104 flag = true;105 break;106 }107 }108 109 if (!flag) {110 puts("none");111 return ;112 }113 114 int ans = 1, ansp = -1;115 int l = 1, r = len, mid;116 117 while (l <= r) {118 mid = (l + r) >> 1;119 if (judge(mid)) {120 ans = mid;121 ansp = rp;122 l = mid + 1;123 } else {124 r = mid - 1;125 }126 }127 128 printf("%d %d\n", ans, ansp);129 }130 131 int main() {132 ios::sync_with_stdio(false);133 #ifndef ONLINE_JUDGE134 freopen("data.in", "r", stdin);135 freopen("data.out", "w", stdout);136 #endif137 138 init();139 while (scanf("%d", &m)!=EOF && m) {140 scanf("%s", s);141 solve();142 }143 144 145 #ifndef ONLINE_JUDGE146 printf("time = %d.\n", (int)clock());147 #endif148 149 return 0;150 }

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

你可能感兴趣的文章