Codeforces 1200E – Compress Words

题目链接:Codeforces 1200E

维护一个字符串$r$表示答案,然后对于每一个字符串$s_i$,和相同长度的$r$的后缀$r_{s}$拼接起来($s_i$在前,$r_s$在后),求$\rm fail$函数,得到最长公共前后缀的长度,取当前字符串的长度取一个最小值,这个值就是$s_i$添加到$r$中之前要删除的前缀的长度。

渐进时间复杂度$O(n)$。

 

说点什么

avatar
50
  Subscribe  
提醒