【HDOJ】4426 Palindromic Substring

综合性很强的一道题目，结合manacher，后缀数组，哈希，RMQ，二分可解。
基本思路是通过manacher可以找到所有可能的回文串，哈希去重，后缀数组二分找数目。最后暴力求解。
需要注意kth需要为__int64。

  1 /* 4426 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;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<unsigned __int64> 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<m; ++i) wc[i] = 0;
 95     for (i=0; i<n; ++i) wc[x[i]=r[i]]++;
 96     for (i=1; i<m; ++i) wc[i] += wc[i-1];
 97     for (i=n-1; i>=0; --i) sa[--wc[x[i]]] = i;
 98     for (j=1,p=1; p<n; j*=2, m=p) {
 99         for (p=0,i=n-j; i<n; ++i) y[p++] = i;
100         for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i]-j;
101         for (i=0; i<n; ++i) wv[i] = x[y[i]];
102         for (i=0; i<m; ++i) wc[i] = 0;
103         for (i=0; i<n; ++i) wc[wv[i]]++;
104         for (i=1; i<m; ++i) wc[i] += wc[i-1];
105         for (i=n-1; 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<n; ++i)
107             x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++;
108     }
109 }
110 
111 void calheight(int *r, int *sa, int n) {
112     int i, j, k = 0;
113 
114     for (i=1; i<=n; ++i) rrank[sa[i]] = i;
115     for (i=0; i<n; height[rrank[i++]]=k)
116     for (k?k--:0, j=sa[rrank[i]-1]; r[j+k]==r[i+k]; ++k) ;
117 }
118 
119 void init_RMQ(int n) {
120     int i, j;
121 
122     for (i=1; i<=n; ++i)
123         dp[i][0] = height[i];
124     dp[1][0] = INF;
125     for (j=1; (1<<j)<=n; ++j)
126         for (i=1; i+(1<<j)-1<=n; ++i)
127             dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
128 }
129 
130 int RMQ(int l, int r) {
131     if (l > 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<<k)+1][k]);
141 }
142 
143 void Manacher(char *s, int *P, int n) {
144     pal.clr();
145     st.clr();
146 
147     int i, j, mx = 0, id = 0;
148 
149     for (i=1; i<n; ++i) {
150         P[i] = mx>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<i+P[i]; ++j) {
155                 int l = 2*i-j, r = j;
156                 l >>= 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 most
180     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 most
193     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('
');
224 }
225 
226 void printHeight(int n) {
227     for (int i=1; i<=n; ++i)
228         printf("%d ", height[i]);
229     putchar('
');
230 }
231 
232 int main() {
233     ios::sync_with_stdio(false);
234     #ifndef ONLINE_JUDGE
235         freopen("data.in", "r", stdin);
236         freopen("data.out", "w", stdout);
237     #endif
238 
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 sa
252         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 Hash
260         init_Hash(n);
261 
262         // init Manacher
263         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] = '';
271         Manacher(ss, P, l);
272 
273         // find count of palindromic
274         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
", ans);
301         }
302         putchar('
');
303     }
304 
305     #ifndef ONLINE_JUDGE
306         printf("time = %d.
", (int)clock());
307     #endif
308 
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**3
10         lc = list(string.lowercase)
11         uc = list(string.uppercase)
12         fout.write("%d
" % (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, q))
17             line = ""
18             for j in xrange(n):
19                 idx = randint(0, 25)
20                 line += lc[idx]
21             fout.write("%s
" % (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)) + "
")
29                 
30                 
31 def MovDataIn():
32     desFileName = "F:eclipse_prjworkspacehdojdata.in"
33     shutil.copyfile("data.in", desFileName)
34 
35     
36 if __name__ == "__main__":
37     GenDataIn()
38     MovDataIn()