mengbierr

一个蒟蒻的博客

5月28

BZOJ1396: 识别子串&&2865: 字符串识别

枚举从每个位置i开始的最短识别子串,显然子串长度L等于max(ht[rk[i]],ht[rk[i]+1])+1,然后分两种情况:
1.在这个子串中的位置,可以用这个子串当做识别子串。
2.在这个子串后的位置,可以用当前位置j-i+1的子串当做识别子串。
两棵线段树维护1情况子串最小值和2情况合法的最大位置即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注