专项测试-字符串2
T1 肃正协议
题意：一个区间是上一个区间的真子串且区间不相交，求最大区间数
设f[i]表示以i作为第一个串的第一项，答案的最大值
满足
- f[i]<=f[i+1]+1
- 答案的范围不超过\(O(\sqrt n)\)
就可以从后往前推，f[i]从f[i+1]+1递减判断是否合法
判断时可以将真子串这个限制进一步缩小
一个区间(i,j)是另一个区间(a,b)的真子串，那么一定存在\(a'\in[a,b],b'\in[a,b],且a'
于是一个长度len，f[i]=len合法仅当s[i,i+len-2]，s[i+1,i+len-1]在i+len-1之后已经成为了合法起始串
unordered_map动态维护合法起始串，在len--时顺便将以i+len-1为起点的合法起始串加进unordered_map
复杂度\(O(n\sqrt n)\)
代码
#include
using namespace std;
#define ull long long
const int N=5e5+11;
const ull p=9973;
char tx[N];
int n;
int f[N];
ull hs[N],mi[N]={1};
unordered_map mp;
inline int max_(int x,int y){return x>y?x:y;}
int main()
{
scanf("%s",tx+1);
n=strlen(tx+1);
for(int i=1;i<=n;++i) mi[i]=mi[i-1]*p,hs[i]=hs[i-1]*p+tx[i]-'a'+1;
int ans=0;
ull hs1;
for(int len,st,i=n;i;--i)
{
f[i]=1;
st=f[i+1]+1;
while(st)
{
if(st==1) break;
if(mp.find(hs[i+st-2]-hs[i-1]*mi[st-1])!=mp.end()||mp.find(hs[i+st-1]-hs[i]*mi[st-1])!=mp.end()){f[i]=st;break;}
--st;
len=f[i+st];
while(len)
{
hs1=hs[i+st+len-1]-hs[i+st-1]*mi[len];
if(mp.find(hs1)!=mp.end()) break;
mp[hs1]=1;
--len;
}
}
ans=max_(ans,f[i]);
}
cout< T2 虚空恶魔
题意：一个区间是另一个区间的子串且不相交，求max(len1* len2)
可以先考虑两个相同且长度为len的串[i,j],[a,b]，i<=j 对于所有和[i,j]本质相同的串，对答案贡献最大的一对满足一个j最小，另一个a最大，也就是取两边的 sam上每个节点维护最小和最大的endpos就行了 没看懂题解，待补
代码
#includeT3 高维入侵