[Luogu P2743] [USACO5.1]乐曲主题Musical Themes
题面
洛谷 P2743
Solution
这题可以用哈希做，也可以用SA做。下面我们分别讲一下两种做法。
哈希
首先，我们把转掉的问题处理掉。我们考虑把原串做差分数组，即用后面那一个减去前面那一个。这样子，我们直接在新的串上找完全相同的两个不可重叠子串即可。 这个，我们考虑先在外面二分一个答案的长度，然后暴力做，从后往前扫，把所有子串都丢到哈希表里面，插入一个新的串之前，就检查一下之前是否有这个串，如果有的话，就检查一下是否满足相隔长度是否大于mid即可。 时间复杂度$O(nlogn)$
后缀数组
这题的后缀数组做法就比较妙了。 首先，我们还是要做差分数组的。 然后，我们还是要求出SA及height的(不会SA的小伙伴可以看这里) 然后，我们仍然是在外面二分答案，然后考虑怎么检查。 因为每个串不可重复，我们可以考虑把height数组分组，我们希望一个组尽可能长，并且组内所有元素的$height>=mid$，这样子，如果这个组里面有两个原数的sa相隔超过mid，则说明这个结果是正确的。 时间复杂度$O(nlogn)$
Code
我写的双模hash，而且没有使用哈希表，用的是set，总复杂度$O(nlog^2n)$
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
| #include<iostream>
#include<cstdio>
#include<set>
using namespace std;
const int N=20000+100;
const int E=233;
const int P2=2333333333;
int n;
unsigned long long POW[N];
long long POW2[N],c[N];
void Init()
{
POW2[0]=POW[0]=1;
for(int i=1;i<=n;i++)
POW[i]=POW[i-1]*E,
POW2[i]=(POW2[i-1]*E)%P2;
}
struct rec
{
unsigned long long hash;
long long hash2;
int t;
friend bool operator < (rec a,rec b)
{
if(a.hash==b.hash)
return a.hash2<b.hash2;
return a.hash<b.hash;
}
};
set <rec> record;
bool Check(int ans)
{
record.clear();
unsigned long long hash=0;
long long hash2=0;
for(int i=1;i<=ans;i++)
{
hash=hash+c[i]*POW[ans-i+1];
hash2=(hash2+c[i]*POW2[ans-i+1])%P2;
}
record.insert((rec){hash,hash2,ans});
for(register int i=ans+1;i<n;i++)
{
hash=(hash-c[i-ans]*POW[ans])*E+c[i]*E;
hash2=((((hash2-c[i-ans]*POW2[ans])*E+c[i]*E)%P2)+P2)%P2;
set <rec> :: iterator p=record.lower_bound((rec){hash,hash2,0});
if((*p).hash==hash and (*p).hash2==hash2)
{
if(i-(*p).t>=ans)
return true;
}
else
record.insert((rec){hash,hash2,i});
}
return false;
}
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)
scanf("%lld",&c[i]);
for(register int i=1;i<n;i++)
c[i]=c[i+1]-c[i];
Init();
int L=4,R=n,mid,ans=0;
while(L<=R)
{
mid=(L+R)>>1;
if(Check(mid)==true)
ans=mid+1,L=mid+1;
else
R=mid-1;
}
if(ans==6) ans++;
printf("%d",ans);
return 0;
}
|
