[SNOI2019]字符串

[SNOI2019]字符串

降智题

 

法一：

后缀数组+sort

听说过不去

 

法二：

删a<删b

只要比较黄色部分字典序即可

lcp[i]维护lcp(i,i+1)后缀的lcp

sort

法三：

因为连续相同删除任何一个结果一样

就把连续相同的合在一起

可以通过相邻的s[i],s[j]判断删除谁更优

发现，倒着考虑，可以直接通过判断s[i],s[j]谁更优，决定i是最小字典序还是最大字典序

链表模拟即可