spoj 694

給出一個字符串，求字符串中不相同的子串個數(shù)。

我們可以知道，字符串中的每個子串都是某個后綴的前綴，于是題目轉(zhuǎn)化為求不相同的后綴的前綴問題。對于每一個SA[k]開始的后綴，將會增加n?SA[k]+1個后綴，而其中height[k]個是和前面的字符串的前綴是相同的。所以答案就是所有n?SA[k]+1?height[k]的總和

#include<cstdio> #include<cstring> #include<algorithm> #define ms(i, j) memset(i, j, sizeof i) #define FN2 "spoj694" using namespace std;const int MAXN = 1000 + 5;char s[MAXN]; int n, m, a[MAXN], tp[MAXN], rk[MAXN], SA[MAXN], tax[MAXN], height[MAXN];bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];} void build() {for (int i=0;i<m;i++) tax[i] = 0;for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;for (int i=1;i<m;i++) tax[i] += tax[i-1];for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;int p;for (int k=1;k<=n;k*=2) {p = 0;for (int i=n-k;i<n;i++) tp[p++] = i;for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i]-k;for (int i=0;i<m;i++) tax[i] = 0;for (int i=0;i<n;i++) tax[rk[tp[i]]]++;for (int i=1;i<m;i++) tax[i] += tax[i-1];for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];swap(rk, tp), p = 0, rk[SA[0]] = 0;for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;if (++p>=n) break;m = p;} } void getH() {int k = 0;for (int i=0;i<n;i++) {if (k) k--;int j = SA[rk[i]-1];while (a[i+k]==a[j+k]) k++;height[rk[i]] = k;} } void init() {scanf("%s", s);n = strlen(s) + 1;for (int i=0;i<n-1;i++) a[i] = s[i];m = 128, a[n-1] = 0; } void solve() {build(), getH();int ans = 0;for (int i=1;i<n;i++) {ans += (n-1) - SA[i] - height[i];}printf("%d\n", ans); } int main() {#ifndef ONLINE_JUDGEfreopen(FN2".in","r",stdin);freopen("1.out","w",stdout);#endifint kase; scanf("%d", &kase);while(kase--) init(), solve();return 0; }

總結(jié)

以上是生活随笔為你收集整理的|spoj 694|后缀数组|Distinct Substrings的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。