这个题好有趣>w<

大致做法可以看吨老师题解qwq

为了让这个题稍微好写一点需要简化一下做法qwq

其实前置技能中除了点分治都是不必要的哟>w<

考虑每一部分都怎么做qwq

求prev就是个kmp好像也没什么困难的地方qwq 可以顺便求出每个串的周期qwq

求suff可以对trie dfs得到SA类似物，然后只要二分x反串在这个SA里的位置，求一下lcp就可以了哟>w<

需要实现一个正串和反串的比较以及lcp，只要求出u这个点往上2^k步的正串反串的rank然后瞎搞搞就可以了哟>w<

求val(x)的最大表示好难的>_< 首先吨老师的题解里只统计了str(A,B)没有统计str(B,A)哦>_<

换句话说val(x)正串反串的最大表示都要求>_<

没有想到什么好做的方法所以只能强行求啦>_<

搞个类似栈的东西每次在末尾加入一个significant的后缀>_< 感觉还是好麻烦可以看看Tomasz Kociumaka CPM16的slides

其实这里正反是很相似地但是不知道怎么写在一起所以感觉几乎一样的写了两遍>_<

最后就是统计答案>w< 由于你懒得写字符串比较所以只能hash啦>w< 区间并直接扫一下就好了也不需要线段树>w<

所以就这样做完啦>w< 感觉还是很愉悦呢！

把代码压进2K的重任就交给各位小哥哥了啦！

比std跑得慢好气啊TAT

对原树做kmp时间复杂度退化到O(n^2)了然而并卡不掉qwq