题目：不同子串个数

这题需要利用后缀数组求出的height的性质，我们发现对于每个后缀，他的height后的所有子串就是算在答案里，因此答案只需要求出n-height[i]-sa[i]+1的和就可以了。

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

const int N = 1e5 + 5;

using namespace std;

char s[N];

int n, rk[N], sa[N], psa[N], k1[N], k2[N], cnt[N], m, height[N];

void get_sort()

{

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

	    cnt[(int)s[i]]++;

	for(int i = 1; i < m; i++)

	    cnt[i] += cnt[i - 1];

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

	    rk[i] = cnt[(int)s[i]] - 1;

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

	{

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

		{

			if(i + w >= n)

			    k2[i] = 0;

			else

			    k2[i] = rk[i + w];

			k1[i] = rk[i];

		}

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

		    cnt[i] = 0;

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

		    cnt[k2[i]]++;

		for(int i = 1; i < m; i++)

		    cnt[i] += cnt[i - 1];

		for(int i = n - 1; i >= 0; i--)

		    psa[--cnt[k2[i]]] = i;

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

		    cnt[i] = 0;

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

		    cnt[k1[i]]++;

		for(int i = 1; i < m; i++)

		    cnt[i] += cnt[i - 1];

		for(int i = n - 1; i >= 0; i--)

		    sa[--cnt[k1[psa[i]]]] = psa[i];

		int tmp = 1;

		rk[sa[0]] = 1;

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

		    if(k1[sa[i]] == k1[sa[i - 1]] && k2[sa[i]] == k2[sa[i - 1]])

		        rk[sa[i]] = tmp;

		    else

		        rk[sa[i]] = ++tmp;

		if(tmp == n)

		    break;

	}

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

	    rk[sa[i]] = i;

}

void get_h()

{

	int begin = 0;

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

	{

		if(!rk[i])

		    continue;

		int j = sa[rk[i] - 1];

		while(s[begin + i] == s[begin + j])

		    begin++;

		height[rk[i]] = begin;

		if(begin)

		    begin--;

	}

}

int main()

{

	scanf("%d %s", &n, s);

	n = strlen(s);

	m = max(n, 300);

	get_sort();

	get_h();

	long long ret = 0;

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

	    ret +=  n - height[i] - sa[i];

	printf("%lld\n", ret);

	return 0;

}

巴特西

2022春每日一题：Day 16

题目：不同子串个数

最新文章

热门文章