spoj705( 求不相同的子串个数)

本文主要是介绍spoj705( 求不相同的子串个数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求串s的不同子串的个数

解题思路：任何子串都是某个后缀的前缀，对n个后缀排序，求某个后缀的前缀的个数，减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#include<vector>
#define N 50005
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6using namespace std;
char s[N];
int r[N],wa[N],wb[N],wv[N],WS[N],sa[N];
bool cmp(int *r,int a,int b,int l)
{return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int n,int m)
{int i, j, p, *x = wa, *y = wb, *t;for(i = 0; i < m; i++)  WS[i] = 0;for(i = 0; i < n; i++)  WS[ x[i] = r[i] ]++;for(i = 1; i < m; i++)  WS[i] += WS[i-1];for(i = n-1; i >= 0; i--)   sa[ --WS[ x[i] ] ] = i;for(j = 1,p = 1; p < n; j*=2, m = p){for(p = 0,i = n-j; i < n; i++)  y[p++] = i;for(i = 0; i < n; i++)  if(sa[i] >= j)  y[p++] = sa[i] - j;for(i = 0; i < n; i++)  wv[i] = x[ y[i] ];for(i = 0; i < m; i++)  WS[i] = 0;for(i = 0; i < n; i++)  WS[ wv[i] ]++;for(i = 1; i < m; i++)  WS[i] += WS[i-1];for(i = n-1; i >= 0; i--)   sa[ --WS[ wv[i] ] ] = y[i];for(t = x,x = y,y = t,p = 1,x[ sa[0] ] = 0, i = 1; i < n; i++)x[ sa[i] ] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;}
}
int rank[N],height[N];
void calheight(int n)
{int i,j,k = 0;for(i = 1; i <= n; i++) rank[ sa[i] ] = i;for(i = 0; i < n; height[ rank[i++] ] = k)for(k ? k-- : 0, j = sa[ rank[i] - 1 ]; r[i+k] == r[j+k]; k++);
}
void solve(int n)
{int ans = 0;int i;//  for(i = 1; i <= n; i++) cout<<sa[i]<<" ";cout<<endl;
//    for(i = 1; i <= n; i++) cout<<height[i]<<" ";cout<<endl;for(int i = 1; i <= n; i++)ans += (n-sa[i]-height[i]);printf("%d\n",ans);
}
int main()
{int t;scanf("%d",&t);while(t--){int i;scanf("%s",s);int n = strlen(s);for(i = 0; i < n; i++)r[i] = s[i]+1;r[n] = 0;da(n+1,130);calheight(n);//    for(i = 0; i <= n; i++)//      cout<<height[i]<<" ";// cout<<endl;solve(n);}return 0;
}

这篇关于spoj705( 求不相同的子串个数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---