Readme

3031.Minimum-Time-to-Revert-Word-to-Initial-State-II

解法1

本题的题意是说，在字符串里寻找一个最长的后缀长度len，使得该后缀同时也是字符串的前缀，并且要求n-len是k的整数。

如果没有第二个要求，那么本题就是一个非常典型的最长公共前后缀问题，用KMP算法的预处理代码，就可以求得一个数组next[i]，表示对于s[0:i]而言的最长公共前后缀长度。即如果next[i]=L，那么就有s[0:L-1] = s[i-L+1:i]. （注意，这里所说的最长公共前后缀都不能包括字符串本身。）

当我们查看len = next[n-1]但是发现不满足n-len能被k整除怎么办？显然，我们希望尝试word的“第二长的公共前后缀”。那么这个怎么求呢？其实因为s[0:len-1] = s[n-len:n-1]已经是s的最长公共前后缀，那么s[0:len-1]的“最长公共前后缀”必然也是s的“公共前后缀”，并且就是第二长的。所以我们只需要求s[0:len-1]的“最长公共前后缀”即可，那就是next[len-1]。依次类推，我们可以求得s的第二长、第三长...的公共前后缀len。只要发现n-len是k的整数倍，就可以知道需要切几刀。如果始终不符合条件，那么就意味着要将整个长度n都切完才行。

解法2

本题可以直接暴力。使用cpp的函数memcpy可以高效判断两段相同长度的内存空间里的字节是否相等。

int memcmp(const void *s1, const void *s2, size_t n);

返回值为零表示相等。