當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

The 15th UESTC Programming Contest Preliminary H - Hesty Str1ng cdoj1551

發布時間：2023/11/29 编程问答 24 豆豆

生活随笔收集整理的這篇文章主要介紹了 The 15th UESTC Programming Contest Preliminary H - Hesty Str1ng cdoj1551 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

地址：http://acm.uestc.edu.cn/#/problem/show/1551

題目：

Hesty Str1ng

Time Limit: 3000/1000MS (Java/Others) ??? Memory Limit: 65535/65535KB (Java/Others)

A chrysanthemum was painted on the second page, and we tried to use the magic power learned just now.

The beautiful flower was compacted to a colorful string?

As known, if we try to choose a substring?

The poetry told us the key to the eternity living secret is the number of the?distinct?palindrome strings made by the method above.

Two strings are considered different if and only if there are different characters in the same position of two strings.

Input

Only one line contains the string?

Output

The key to the eternity living secret.

Sample input and output

Sample InputSample Output

abc

Hint

The palindrome strings can be made are "aba", "bcb", "abcba".

思路：

　　對于一個長度為n的子串，如果在其后連接一個長度為x（1<=x<n）的字符串形成新串T，并且T為回文串。

　　n=1時：形成的T的數量=0

　　n>1時：形成的T的數量=1+sum.（sum：子串含有的不同回文后綴的數量）

　　回顧下計算不同子串個數的后綴數組做法：

　　下面先給出一個結論：

　　　　sum[x]:表示后綴s[x....n-1]中s[k]==s[k+1]的個數

　　　　ans=∑（n-sa[i]-height[i]+sum[sa[i]+height[i]]) （字符串下標從0開始。）

　　　　并且當

　　　　　　　height[i]==0時　　ans-=1;

　　　　　　　height[i]>=2&&ss[sa[i]+height[i]-1]==ss[sa[i]+height[i]]時　　ans+=1;

　　　　　　　!height[i]&&ss[sa[i]+height[i]]==ss[sa[i]+height[i]+1]時　　ans-=1;

　　　　上面對應的三種情況分別是：

　　　　1. 此時有排序后的后綴abbb,ba.

　　　　2.??此時有排序后的后綴abb,abbba

　　　　3.?此時有排序后的后綴a,bba

　　具體證明過程我就不寫了（PS：其實是我也不太會）

?　　參考自校隊另一位dalao的博文：http://blog.csdn.net/prolightsfxjh/article/details/66970491

　　具體見代碼

1 #include <cstdlib> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 const int N = 100005; 7 int wa[N], wb[N], ws[N], wv[N]; 8 int s[N],sa[N],rank[N], height[N]; 9 char ss[N]; 10 int sum[N]; 11 bool cmp(int r[], int a, int b, int l) 12 { 13 return r[a] == r[b] && r[a+l] == r[b+l]; 14 } 15 16 void da(int r[], int sa[], int n, int m) 17 { 18 int i, j, p, *x = wa, *y = wb; 19 for (i = 0; i < m; ++i) ws[i] = 0; 20 for (i = 0; i < n; ++i) ws[x[i]=r[i]]++; 21 for (i = 1; i < m; ++i) ws[i] += ws[i-1]; 22 for (i = n-1; i >= 0; --i) sa[--ws[x[i]]] = i; 23 for (j = 1, p = 1; p < n; j *= 2, m = p) 24 { 25 for (p = 0, i = n - j; i < n; ++i) y[p++] = i; 26 for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; 27 for (i = 0; i < n; ++i) wv[i] = x[y[i]]; 28 for (i = 0; i < m; ++i) ws[i] = 0; 29 for (i = 0; i < n; ++i) ws[wv[i]]++; 30 for (i = 1; i < m; ++i) ws[i] += ws[i-1]; 31 for (i = n-1; i >= 0; --i) sa[--ws[wv[i]]] = y[i]; 32 for (std::swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; ++i) 33 x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++; 34 } 35 } 36 37 void calheight(int r[], int sa[], int n) 38 { 39 int i, j, k = 0; 40 for (i = 1; i <= n; ++i) rank[sa[i]] = i; 41 for (i = 0; i < n; height[rank[i++]] = k) 42 for (k?k--:0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++); 43 } 44 45 int main() 46 { 47 int len; 48 long long ans=0; 49 scanf("%s",ss); 50 len=strlen(ss); 51 for(int i=0;i<len;i++) 52 s[i]=ss[i]-'a'+1; 53 s[len]=0; 54 da(s,sa,len+1,28); 55 calheight(s,sa,len); 56 for(int i=len-1;i>=0;i--) 57 if(ss[i]==ss[i+1]) sum[i]=sum[i+1]+1; 58 else sum[i]=sum[i+1]; 59 for(int i=1;i<=len;i++) 60 { 61 if(height[i]==0)ans--; 62 ans+=sum[sa[i]+height[i]]+len-sa[i]-height[i]; 63 if(height[i]>=2&&ss[sa[i]+height[i]-1]==ss[sa[i]+height[i]]) 64 ans++; 65 if(!height[i]&&ss[sa[i]+height[i]]==ss[sa[i]+height[i]+1]) 66 ans--; 67 //printf("x==%d %lld\n",i,ans); 68 } 69 printf("%lld\n",ans); 70 return 0; 71 }

轉載于:https://www.cnblogs.com/weeping/p/6640878.html

總結

以上是生活随笔為你收集整理的The 15th UESTC Programming Contest Preliminary H - Hesty Str1ng cdoj1551的全部內容，希望文章能夠幫你解決所遇到的問題。

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