首页 > 代码库 > 【SPOJ】694. Distinct Substrings
【SPOJ】694. Distinct Substrings
http://www.spoj.com/problems/DISUBSTR/
题意:求字符串不同子串的数目。
#include <bits/stdc++.h>using namespace std;const int N=1005;void sort(int *x, int *y, int *sa, int n, int m) { static int c[N], i; for(i=0; i<m; ++i) c[i]=0; for(i=0; i<n; ++i) ++c[x[y[i]]]; for(i=1; i<m; ++i) c[i]+=c[i-1]; for(i=n-1; i>=0; --i) sa[--c[x[y[i]]]]=y[i];}void hz(int *a, int *sa, int n, int m) { static int t1[N], t2[N], i, j, p, *x, *y, *t; x=t1, y=t2; for(i=0; i<n; ++i) x[i]=a[i], y[i]=i; sort(x, y, sa, n, m); for(j=1, p=1; p<n; j<<=1, m=p) { p=0; for(i=n-j; i<n; ++i) y[p++]=i; for(i=0; i<n; ++i) if(sa[i]-j>=0) y[p++]=sa[i]-j; sort(x, y, sa, n, m); for(t=x, x=y, y=t, p=1, x[sa[0]]=0, i=1; i<n; ++i) x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p-1:p++; }}void geth(int *s, int *sa, int *h, int n) { static int rank[N], j, i, k; for(i=1; i<=n; ++i) rank[sa[i]]=i; for(k=0, i=1; i<=n; h[rank[i++]]=k) for(k?--k:0, j=sa[rank[i]-1]; s[i+k]==s[j+k]; ++k);}int a[N], sa[N], h[N], n;char s[N];int main() { int cs; scanf("%d", &cs); while(cs--) { scanf("%s", s+1); n=strlen(s+1); for(int i=1; i<=n; ++i) a[i]=s[i]; hz(a, sa, n+1, 128); geth(a, sa, h, n); int ans=0; for(int i=1; i<=n; ++i) ans+=n-sa[i]+1-h[i]; printf("%d\n", ans); } return 0;}
经典题....首先每个后缀的前缀就是一个子串,因此每个后缀可以构成这个后缀长度大小那么多个子串。但是我们要考虑重合的情况,即我们剪掉与上一个后缀子串相同前缀的height值就好啦
【SPOJ】694. Distinct Substrings
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。