【HDOJ】4426 Palindromic Substring-白红宇

【HDOJ】4426 Palindromic Substring

阅读量：6858 次

发布时间：2019-06-26

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

综合性很强的一道题目，结合manacher，后缀数组，哈希，RMQ，二分可解。

基本思路是通过manacher可以找到所有可能的回文串，哈希去重，后缀数组二分找数目。最后暴力求解。

需要注意kth需要为__int64。

1 /* 4426 */  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 __int64 mod = 777777777LL; 44 const int seed = 50009; 45 const int INF = 0x3f3f3f3f; 46 const int maxn = 1e5+5; 47 // input 48 char s[maxn]; 49 int val[26]; 50 __int64 V[maxn]; 51 // manacher 52 char ss[maxn*2]; 53 int P[maxn*2]; 54 // sa 55 int a[maxn]; 56 int height[maxn], sa[maxn], rrank[maxn]; 57 int wa[maxn], wb[maxn], wc[maxn], wv[maxn]; 58 // RMQ 59 int dp[maxn][17]; 60 // Hash 61 unsigned __int64 H[maxn]; 62 // init 63 unsigned __int64 Base[maxn], Power[maxn]; 64 vpii pal; 65 set
                                  
                                    st; 66 67 void init() { 68 Base[0] = Power[0] = 1; 69 rep(i, 1, maxn) { 70 Base[i] = 1LL * Base[i-1] * 26 % mod; 71 Power[i] = 1LL * Power[i-1] * seed; 72 } 73 } 74 75 void init_Hash(int n) { 76 H[0] = s[0] - 'a' + 1; 77 rep(i, 1, n) 78 H[i] = H[i-1] * seed + s[i]-'a'+1; 79 } 80 81 unsigned __int64 getHash(int l, int r) { 82 if (l == 0) 83 return H[r]; 84 return H[r] - H[l-1] * Power[r-l+1]; 85 } 86 87 bool cmp(int *r, int a, int b, int l) { 88 return r[a]==r[b] && r[a+l]==r[b+l]; 89 } 90 91 void da(int *r, int *sa, int n, int m) { 92 int i, j, *x=wa, *y=wb, *t, p; 93 94 for (i=0; i
                                   
                                    =0; --i) sa[--wc[x[i]]] = i; 98 for (j=1,p=1; p
                                    
                                     = j) y[p++] = sa[i]-j;101 for (i=0; i
                                     
                                      =0; --i) sa[--wc[wv[i]]] = y[i];106 for (t=x,x=y,y=t,p=1,x[sa[0]]=0, i=1; i
                                      
                                        r)132 swap(l, r);133 134 ++l;135 int k = 0;136 137 while (1<<(k+1) <= r-l+1)138 ++k;139 140 return min(dp[l][k], dp[r-(1<
                                       
                                        i ? min(P[2*id-i], mx-i) : 1;151 while (s[i+P[i]] == s[i-P[i]])152 ++P[i];153 if (i+P[i] > mx) {154 for (j=mx; j
                                        
                                         >= 1;157 r = (r & 1) ? (r>>1) : (r>>1)-1;158 if (l > r)159 continue;160 161 unsigned __int64 hval = getHash(l, r);162 if (st.find(hval) == st.end()) {163 st.insert(hval);164 pal.pb(mp(l, r));165 }166 }167 mx = i + P[i];168 id = i;169 }170 }171 }172 173 int getCnt(int fr, int to, int n) {174 int len = to - fr + 1;175 int rankfr = rrank[fr];176 int l, r, mid, tmp;177 int L = rankfr, R = rankfr;178 179 // find left most180 l = 1, r = rankfr - 1;181 while (l <= r) {182 mid = (l + r) >> 1;183 tmp = RMQ(mid, rankfr);184 if (tmp >= len) {185 L = mid;186 r = mid - 1;187 } else {188 l = mid + 1;189 }190 }191 192 // find right most193 l = rankfr + 1, r = n;194 while (l <= r) {195 mid = (l + r) >> 1;196 tmp = RMQ(rankfr, mid);197 if (tmp >= len) {198 R = mid;199 l = mid + 1;200 } else {201 r = mid - 1;202 }203 }204 205 return R - L + 1;206 }207 208 void init_Val(int n) {209 V[0] = val[s[0]-'a'];210 rep(i, 1, n)211 V[i] = (V[i-1] * 26 + val[s[i]-'a']) % mod;212 }213 214 __int64 getVal(int l, int r) {215 if (l == 0)216 return V[r];217 return (V[r] - V[l-1] * Base[r-l+1]%mod + mod) % mod;218 }219 220 void printSa(int n) {221 for (int i=1; i<=n; ++i)222 printf("%d ", sa[i]);223 putchar('\n');224 }225 226 void printHeight(int n) {227 for (int i=1; i<=n; ++i)228 printf("%d ", height[i]);229 putchar('\n');230 }231 232 int main() {233 ios::sync_with_stdio(false);234 #ifndef ONLINE_JUDGE235 freopen("data.in", "r", stdin);236 freopen("data.out", "w", stdout);237 #endif238 239 int t;240 int n, q;241 __int64 kth;242 int ans;243 vpii vc;244 245 init();246 scanf("%d", &t);247 while (t--) {248 scanf("%d %d", &n, &q);249 scanf("%s", s);250 251 // init sa252 rep(i, 0, n)253 a[i] = s[i]-'a'+1;254 a[n] = 0;255 da(a, sa, n+1, 30);256 calheight(a, sa, n);257 init_RMQ(n);258 259 // init Hash260 init_Hash(n);261 262 // init Manacher263 int l = 0;264 ss[l++] = '@';265 // ss[l++] = '#';266 rep(i, 0, n) {267 ss[l++] = s[i];268 ss[l++] = '#';269 }270 ss[l] = '\0';271 Manacher(ss, P, l);272 273 // find count of palindromic274 int sz = SZ(pal);275 rep(i, 0, sz) {276 wc[i] = getCnt(pal[i].fir, pal[i].sec, n);277 pal[i].sec = (pal[i].fir + pal[i].sec) >> 1;278 }279 280 while (q--) {281 scanf("%I64d", &kth);282 rep(i, 0, 26)283 scanf("%d", &val[i]);284 init_Val(n);285 vc.clr();286 rep(i, 0, sz) {287 int tmp = getVal(pal[i].fir, pal[i].sec);288 vc.pb(mp(tmp, wc[i]));289 }290 sort(all(vc));291 ans = -1;292 rep(i, 0, sz) {293 if (kth <= vc[i].sec) {294 ans = vc[i].fir;295 break;296 } else {297 kth -= vc[i].sec;298 }299 }300 printf("%d\n", ans);301 }302 putchar('\n');303 }304 305 #ifndef ONLINE_JUDGE306 printf("time = %d.\n", (int)clock());307 #endif308 309 return 0;310 }

数据发生器。

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**310         lc = list(string.lowercase)11         uc = list(string.uppercase)12         fout.write("%d\n" % (t))13         for tt in xrange(t):14             n = randint(10**4, 10**5)15             q = randint(30, 40)16             fout.write("%d %d\n" % (n, q))17             line = ""18             for j in xrange(n):19                 idx = randint(0, 25)20                 line += lc[idx]21             fout.write("%s\n" % (line))22             for i in xrange(q):23                 kth = randint(1, 1005)24                 dataList = [kth]25                 for j in xrange(26):26                     val = randint(0, 25)27                     dataList.append(val)28                 fout.write(" ".join(map(str, dataList)) + "\n")29                 30                 31 def MovDataIn():32     desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"33     shutil.copyfile("data.in", desFileName)34 35     36 if __name__ == "__main__":37     GenDataIn()38     MovDataIn()

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

你可能感兴趣的文章

阿里云的江苏故事：人工智能的智造范本

查看>>

浙江省人民政府咨询委员会专访泰一指尚开展课题调研

NetApp CMO：如何释放数据的潜能成为企业核心诉求

查看>>