题意

求一个字符串里面大小互不相同,且大小对应的子串个数。

分析

由于要统计的是子串个数且长度相同,考虑用KMP。

KMP本来是比较长度相同的数,现在是要比较当前的两个数的相对大小是否相同。

也就是说,对于在Next上跳的指针\(k\),以及现在这要比较的位置\(j\),需要保证\(t[j]\)在\([j-k,j]\)中的相对大小和\(k\)在\([0,k]\)中的相对大小一致,否则就是匹配失败了。

相对位置的大小我们可以用树状数组来维护,当\(k\)跳Next的时候,暴力的把加入树状数组的数删除即可。

因为保证每一个数都只加入一次,所以复杂度还是可以保证在\(O(nlogn)\)的。

离散的数组开小了。wa*1

树状数组开小了。wa*2

 


发表评论

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