3031. Minimum Time to Revert Word to Initial State II

Solution idea

KMP

1. 思路接续 3029。但是因为量级增大，之前的解法不再适用。
2. 求最长后缀=前缀，使用 KMP 算法解决。
3. 使用 KMP STEP 1 可以求出最长的后缀=前缀 lsp[(n-1)-j+1 : n-1] (尾巴的长度=j)。**但是注意!**这里有一个问题：切t刀k长度的前缀，不一定刚好可以完整切掉头部，保留下最长的尾巴j。有可能切"多"了，剩下的尾巴长度不足j。此时，我们就需要寻找：第二长的后缀=前缀，第三长的后缀=前缀...
4. 如何找第二长，第三长？这里考察到 KMP算法中很重要的transitive思想!
   • 首先，我们看到word[0:j-1]这一段，其中，lsp[j-1]代表最长的长度j' s.t. word[0:j'-1] == word[(j-1)-j'+1:j-1]
   • 根据传递性(transitive)，我们可以得到 word[0:j'-1] == word[(n-1)-j'+1 : n-1]
   • 这个长度j'就是我们寻找的第二长度的后缀=前缀。
   • 以此类推，第三长度在word[0:j'-1]这一段中找...
   • 不停缩短，直到长度为0，说明我们找不到后缀=前缀，整个字符串都会被切掉。
5. 注意：KMP STEP 1 所找的最长公共前后缀都不能包括字符串本身。否则将失去意义，因为如果包括字符串本身，那么每个lsp[i]最长公共前后缀一定就是word[0:i]本身。代码实现上，不包含本身的处理就是 base case设置为lsp[0] = 0。

一图胜千言

Time complexity = $O(n)$

Resource

【每日一题】LeetCode 3031. Minimum Time to Revert Word to Initial State II