zoj 3661 Palindromic Substring

zoj 3661 Palindromic Substring

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef unsigned int UL;typedef long long LL;const int Mod = 777777777;const int N = 100015;#define mp make_pairchar s[N];UL hashMi[N], hashSum[N];pair<int,int> ans[N*10];int v[27];int tot;struct hashTable{const static int Mod = 500009;int gcnt;int ghead[Mod];struct hashList{int next;UL key;int len;int pos;} ele[N*10];void reset(){memset(ghead, -1, sizeof(ghead));gcnt = 0;}void ins(UL num, int len, int pos){int x = num%Mod;ele[gcnt].next = ghead[x];ele[gcnt].key = num;ele[gcnt].len = len;ele[gcnt].pos = pos;ghead[x] = gcnt++;}int find(UL num, int len){int x = num%Mod;for(int i = ghead[x]; i != -1; i = ele[i].next)if(ele[i].key == num &&ele[i].len == len) return ele[i].pos;return 0;}} ha;UL getHash(int l, int r){UL ret;ret = hashSum[r];if(l)ret -= hashSum[l-1]*hashMi[r-l+1];return ret;}struct Trie{const static int CHILD_NUM = 26;const static int MAX_NODE = N*3; int ID[128]; int val[MAX_NODE]; int chd[MAX_NODE][CHILD_NUM]; int vi[MAX_NODE]; int sz;Trie(){for(int i = 0; i < 26; ++i)ID[i+'a'] = i;}void reset(){memset(chd[0], 0, sizeof(chd[0]));memset(val, 0, sizeof(val));sz = 1;}void ins(char s[], int l, int r, int R, int nid){int j;UL num;for(int i = r; i >=l; --i){j = ID[s[i]];if(!chd[nid][j]){memset(chd[sz], 0, sizeof(chd[sz]));chd[nid][j] = sz++;}nid = chd[nid][j];num = getHash(i,R);ha.ins(num,R-i+1,nid);}++val[nid];}int dfs(int hash, int nid, int mi){int i, u, sum=val[nid];for(i = 0; i < CHILD_NUM; ++i){u = chd[nid][i];if(u){int nextHash = (hash+(LL)v[i]*mi)%Mod;sum += dfs(nextHash, u,(LL)mi*26%Mod);}}if(sum && nid) ans[tot++] = mp(hash,sum);return sum;}} trie;void palindrome(char cs[], int len[], int n) {for (int i = 0; i < n * 2; ++i) {len[i] = 0;}for (int i = 0, j = 0, k; i < n * 2; i += k, j = max(j - k, 0)) {while (i - j >= 0 && i + j + 1 < n * 2 && cs[(i - j) / 2] == cs[(i + j + 1) / 2])j++;len[i] = j;for (k = 1; i - k >= 0 && j - k >= 0 && len[i - k] != j - k; k++) {len[i + k] = min(len[i - k], j - k);}}}int ma[N<<2];const int D = 173;void go(){int len, i;len = strlen(s);palindrome(s, ma, len);hashSum[0] = s[0];for(i = 1; i < len; ++i)hashSum[i] = hashSum[i-1]*D + s[i]; ha.reset(); trie.reset();for(i = 0; i < len; ++i){for(int p=0;p<2;++p){ if(!ma[i<<1|p])continue;int l = i-(ma[i<<1|p]+1)/2+1, l1, pos;l1 = l;UL num = getHash(l,i);while(l<=i && !(pos=ha.find(num,i-l+1))){ ++l; num = getHash(l,i);}trie.ins(s,l1,l-1,i,pos);}}}int main(){int i, tt, Q;for(hashMi[0] = 1, i = 1; i < N; ++i)hashMi[i] = hashMi[i-1]*D;scanf("%d",&tt);while(tt--){scanf("%*d%d",&Q);scanf("%s",s);go();while(Q--){ LL k; cin >> k;for(i=0;i<26;++i) scanf("%d",&v[i]);tot = 0;trie.dfs(0,0,1);sort(ans,ans+tot);for(i=0; i<tot; ++i)if(k>ans[i].second)k-=ans[i].second;else{printf("%dn",ans[i].first);break;}}puts("");}return 0;}