New Distinct Substrings

题目大意

给定一个字符串，求本质不同的子串个数

题解

SA常见思想：每一个子串都是某个后缀的前缀

考虑每一个后缀的贡献，首先他拥有n - sa[i]个(我是用的模板中，sa[i]的大小是0....n-1)前缀，这些前缀有height[i]个跟sa[i-1]相同，要减去。剩下的部分不可能与sa[i-1]之前的想通了，不然sa[i]会排在sa[i-1]前面

还要注意本题的字符集是小写字母（鬼知道样例是什么东西）

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <iostream>

#include <cmath>

void swap(int &a, int &b){int tmp = a;a = b, b = tmp;}

void swap(int* &a, int* &b){int *tmp = a;a = b;b = tmp;}

int max(int a, int b){return a > b ? a : b;}

int min(int a, int b){return a < b ? a : b;}

void read(int &x)

{

	x = 0;char ch = getchar(), c = ch;

	while(ch < '0' || ch > '9') c = ch, ch = getchar();

	while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();

	if(c == '-') x = -x;

}

const int INF = 0x3f3f3f3f;

const int MAXN = 50000 + 10;

struct SuffixArray

{

    int s[MAXN], sa[MAXN], rank[MAXN], height[MAXN];

    int t[MAXN], t2[MAXN], c[MAXN];

    int n;

    void clear(){n = 0;memset(sa, 0, sizeof(sa));}

    void build_sa(int m)

    {

    	++ n;

        int i,*x=t,*y=t2;

    	for(i=0;i<m;++i) c[i]=0;

    	for(i=0;i<n;++i) x[i]=s[i];

    	for(i=0;i<n;++i) c[x[i]]++;

    	for(i=1;i<m;++i) c[i]+=c[i-1];

    	for(i=n-1;i>=0;--i) sa[--c[x[i]]]=i;

    	for(int k=1;k<=n;k<<=1)

    	{

  			int p=0;

   	    	for(i=n-k;i<n;++i) y[p++]=i;

        	for(i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;

        	for(i=0;i<m;++i) c[i]=0;

        	for(i=0;i<n;++i) c[x[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];

        	swap(x,y);

        	p=1;x[sa[0]]=0;

        	for(i=1;i<n;++i)

        	    x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p-1:p++;

        	if(p>=n) break;

        	m=p;

    	}

    	-- n;

    }

    void build_height()

    {

        int i,j,k=0;

   		for(i=1;i<=n;++i) rank[sa[i]]=i;

    	for(i=0;i<n;++i)

    	{

    	    if(k) k--;

    	    j=sa[rank[i]-1];

    	    while(s[i+k]==s[j+k]) k++;

    	    height[rank[i]]=k;

    	}

    }

}A;

int t, ans;

char tmp[MAXN];

int main()

{

	read(t);

	for(;t;-- t)

	{

		ans = 0;

		scanf("%s", tmp);

		A.s[0] = tmp[0] - 'a' + 1;

		for(A.n = 1;tmp[A.n];++ A.n) A.s[A.n] = tmp[A.n] - 'a' + 1;

		A.s[A.n] = 0;

		A.build_sa(30);

		A.build_height();

		//调试信息

		/*for(int i = 1;i <= A.n;++ i)

			printf("sa[%d]:%s\n", i, tmp + A.sa[i]);

		for(int i = 1;i <= A.n;++ i)

		printf("height[%d]:%d\n", i, A.height[i]);	*/

		for(int i = 1;i <= A.n;++ i)

			ans += A.n - A.sa[i] - A.height[i];

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

SPOJ694 New Distinct Substrings

New Distinct Substrings

题目大意

题解

最新文章

热门文章