后綴數組求不重復回文子串數目。注意dp數組。

1 /* 3948 */ 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 int INF = 0x3f3f3f3f; 44 const int maxl = 2e5+5; 45 const int maxn = 4e5+5; 46 char s[maxl], ss[maxl]; 47 int a[maxn]; 48 int height[maxn], rrank[maxn], sa[maxn]; 49 int wa[maxn], wb[maxn], wc[maxn], wv[maxn]; 50 bool visit[maxn]; 51 int dp[19][maxn]; 52 53 bool cmp(int *r, int a, int b, int l) { 54 return r[a]==r[b] && r[a+l]==r[b+l]; 55 } 56 57 void da(int *r, int *sa, int n, int m) { 58 int i, j, *x=wa, *y=wb, *t, p; 59 60 for (i=0; i<m; ++i) wc[i] = 0; 61 for (i=0; i<n; ++i) wc[x[i]=r[i]]++; 62 for (i=1; i<m; ++i) wc[i] += wc[i-1]; 63 for (i=n-1; i>=0; --i) sa[--wc[x[i]]]=i; 64 for (j=1,p=1; p<n; j*=2, m=p) { 65 for (p=0,i=n-j; i<n; ++i) y[p++] = i; 66 for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; 67 for (i=0; i<n; ++i) wv[i] = x[y[i]]; 68 for (i=0; i<m; ++i) wc[i] = 0; 69 for (i=0; i<n; ++i) wc[wv[i]]++; 70 for (i=1; i<m; ++i) wc[i] += wc[i-1]; 71 for (i=n-1; i>=0; --i) sa[--wc[wv[i]]] = y[i]; 72 for (t=x,x=y,y=t, x[sa[0]]=0, p=1,i=1; i<n; ++i) 73 x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1:p++; 74 } 75 } 76 77 void calheight(int *r, int *sa, int n) { 78 int i, j, k = 0; 79 80 for (i=1; i<=n; ++i) rrank[sa[i]] = i; 81 for (i=0; i<n; height[rrank[i++]]=k) 82 for (k?k--:0, j=sa[rrank[i]-1]; r[i+k]==r[j+k]; ++k) ; 83 } 84 85 void printSa(int n) { 86 for (int i=1; i<=n; ++i) 87 printf("%d ", sa[i]); 88 putchar('\n'); 89 } 90 91 void printHeight(int n) { 92 for (int i=1; i<=n; ++i) 93 printf("%d ", height[i]); 94 putchar('\n'); 95 } 96 97 void printRank(int n) { 98 for (int i=1; i<=n; ++i) 99 printf("%d ", rrank[i]); 100 putchar('\n'); 101 } 102 103 void init_RMQ(int n) { 104 int i, j; 105 106 for (i=1; i<=n; ++i) 107 dp[0][i] = height[i]; 108 dp[0][1] = INF; 109 for (j=1; (1<<j)<=n; ++j) 110 for (i=1; i+(1<<j)-1<=n; ++i) 111 dp[j][i] = min(dp[j-1][i], dp[j-1][i+(1<<(j-1))]); 112 } 113 114 int RMQ(int l, int r) { 115 if (l > r) 116 swap(l, r); 117 118 ++l; 119 int k = 0; 120 121 while (1<<(k+1) <= r-l+1) 122 ++k; 123 124 return min(dp[k][l], dp[k][r-(1<<k)+1]); 125 } 126 127 void solve() { 128 int len = strlen(s); 129 int nn = len * 2 + 1, n, nn2 = nn * 2; 130 int l = 0; 131 132 rep(i, 0, len) { 133 a[l] = a[nn2-l] = 2; 134 ++l; 135 a[l] = a[nn2-l] = s[i]-'a'+3; 136 ++l; 137 } 138 a[l] = a[nn2-l] = 2; 139 a[nn] = 1; 140 a[nn2+1] = 0; 141 142 n = nn2 + 1; 143 da(a, sa, n+1, 32); 144 calheight(a, sa, n); 145 146 #ifndef ONLINE_JUDGE 147 // printSa(n); 148 // printHeight(n); 149 #endif 150 151 init_RMQ(n); 152 153 int ans = 0, mn = 0, tmp; 154 155 memset(visit, false, sizeof(visit)); 156 rep(i, 2, n+1) { 157 mn = min(mn, height[i]); 158 if (visit[nn2-sa[i]]) { 159 tmp = RMQ(rrank[sa[i]], rrank[nn2-sa[i]]); 160 if (tmp > mn) { 161 ans += (tmp - mn) >> 1; 162 mn = tmp; 163 } 164 } else { 165 visit[sa[i]] = true; 166 } 167 } 168 169 printf("%d\n", ans); 170 } 171 172 int main() { 173 ios::sync_with_stdio(false); 174 #ifndef ONLINE_JUDGE 175 freopen("data.in", "r", stdin); 176 freopen("data.out", "w", stdout); 177 #endif 178 179 int t; 180 181 scanf("%d", &t); 182 rep(tt, 1, t+1) { 183 scanf("%s", s); 184 printf("Case #%d: ", tt); 185 solve(); 186 } 187 188 #ifndef ONLINE_JUDGE 189 printf("time = %d.\n", (int)clock()); 190 #endif 191 192 return 0; 193 }

數據生成器。

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 fout.write("%d\n" % (t)) 12 for tt in xrange(t): 13 length = randint(50, 105) 14 line = "" 15 for i in xrange(length): 16 idx = randint(0, 5) 17 line += lc[idx] 18 fout.write("%s\n" % (line)) 19 20 21 22 def MovDataIn(): 23 desFileName = "F:\eclipse_prj\workspace\hdoj\data.in" 24 shutil.copyfile("data.in", desFileName) 25 26 27 if __name__ == "__main__": 28 GenDataIn() 29 MovDataIn()

?

轉載于:https://www.cnblogs.com/bombe1013/p/5180829.html

總結

以上是生活随笔為你收集整理的【HDOJ】3948 The Number of Palindromes的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。