hdu 3518 Boring counting 后缀数组

缘起

【1】中使用后缀树切了~ 但是本文采用后缀数组的姿势切. 切法的思想源自罗大神的IOI09年论文的第18页. 即通过lcp数组对后缀进行分类的思想.

分析

题目见【1】好了~ 这里讲一下思想.

其实思想在 【2】中求解最长不重叠重复子串 中已经讲过了. 思想就在【2】的那个图中.

即罗大神说的

使用lcp给所有后缀进行分类是处理字符串问题的一种常用手段.

那怎么用于本题呢? 效仿 【2】, 我们只需要枚举不重叠重复子串的长度k即可. 注意到本题的数据规模较小——仅仅到1000. 所以可以枚举k——从1到n-1. 然后对于固定的k, 使用【2】中的那幅图的思想将后缀进行归类（即lcp对所有后缀进行归类，即lcp>=k的在一组）. 然后判断同一组中的 maxsa-minsa是否>=k, 如果是的话, 表明这一组中长度为k的前缀是不重叠的重复子串. 注意，不同组的后缀的k前缀是不可能相同的, 否则他们就会在一组了。所以不必担心重复计数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 1005, inf = 0x3f3f3f3f;
char s[maxn];
int n,k,r[maxn], sa[maxn], t[maxn], lcp[maxn];

bool c0(int i,int j)
{
	if (r[i]!=r[j])
	{
		return r[i]<r[j];
	}
	int ri = i+k<=n?r[i+k]:-1, rj = j+k<=n?r[j+k]:-1;
	return ri<rj;
}

void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	}
	if (x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}

void da()
{
	n = 0,k=1;
	while(s[n])
	{
		sa[n] = n;
		r[n] = s[n]-'a'+1;
		++n;
	}
	sa[n] = n, r[n] = 0;
	while(k<=n)
	{
		sort(sa, sa+n+1, c0);
		t[sa[0]] = 0;
		for (int i = 1; i<=n; i++)
		{
			t[sa[i]] = t[sa[i-1]]+c0(sa[i-1], sa[i]);
		}
		memcpy(r,t,sizeof(int)*(n+1));
		k<<=1;
	}
}

void height()
{
	int h =0;
	for (int i = 0,j;i<n; i++)
	{
		if (r[i]==1)
		{
			continue;
		}
		j = sa[r[i]-1];
		if (h)
		{
			--h;
		}
		while(i+h<n && j+h<n)
		{
			if (s[i+h]!=s[j+h])
			{
				break;
			}
			++h;
		}
		lcp[r[i]-1] = h;
	}
}

int kk() // k长度的前缀的个数
{
	int minsa = inf, maxsa = -inf, ansk = 0; // ansk是长度为k的符合条件的前缀的个数(即长度为k的重复不重叠子串)
	for (int i = 1; i<n; i++)
	{
		if (lcp[i]<k) // 一组的终结
		{
			if (maxsa-minsa>=k)
			{
				++ansk;
			}
			minsa = maxsa = sa[i+1]; // 开始新的一组
		}
		else
		{
			minsa = min(minsa, min(sa[i], sa[i+1]));
			maxsa = max(maxsa, max(sa[i], sa[i+1]));
		}
	}
	if (maxsa-minsa>=k) // 别漏了最后那组
	{
		++ansk;
	}
	return ansk;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%s",s), s[0]!='#')
	{
		da();
		height();
		int ans = 0;
		k = 1;
		while(k<n) // 枚举前缀长度k
		{
			ans+=kk();
			++k;
		}
		write(ans);
		puts("");
	}
	return 0;
}

ac情况

Status Accepted
Time 93ms
Memory 1232kB
Length 1698
Lang G++
Submitted 2019-10-13 20:19:22
Shared
RemoteRunId 30906121

参考

【1】https://yfsyfs.github.io/2019/08/03/hdu-3518-Boring-counting-%E5%90%8E%E7%BC%80%E6%A0%91/

【2】https://yfsyfs.github.io/2019/10/07/poj-1743-Musical-Theme-%E4%BA%8C%E5%88%86%E7%AD%94%E6%A1%88-%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84/