T3 午枫的字符串移动 题目大意 给定原串和最终串，最终串是通过原串循环右移且丢失若干字符得到的，求出原串最小的循环右移次数。 题解思路 由于 nnn 最大是 100001000010000 ，我们可以考虑 O(n2)O(n^2)O(n2) 的做法。 首先，很容易发现 mmm 最大可能是 n−1n-1n−1 ，所以我们可以通过枚举 s′s's′ 对应原串 sss 的开头位置，类比做了 C(s,m)C(s,m)C(s,m) 的操作，一位一位进行比较判断，如果某一位不匹配，那么就让 sss 的下一位去匹配，如果 sss 的每一位都判断过了还没有匹配到 s′s's′ 的最后一位，那么说明不存在这么一个 mmm 让 sss 变成 s′s's′ 。 我们只要找到最小的 mmm 即可。 参考代码

这题有一个很引人注目的点：n≤104n \leq 10^4n≤104。这意味着允许 O(n2)O(n^2)O(n2) 算法！ 首先考虑到移动 nnn 次等于不动，所以求得 0≤m<n0 \leq m<n0≤m<n。 直接枚举 mmm，然后模拟移动的过程，最后判断是否和 s′s's′ 恰好相差 kkk 字符。 判断可以使用双指针，如果 sl=sr′s_l=s'_rsl =sr′ ，则成功匹配；反之匹配失败，需要在 sr′s'_rsr′ 前添加一个字符。统计添加的字符数量是否恰好为 kkk 即可。 时间复杂度：O(n2)O(n^2)O(n2) 空间复杂度：O(n)O(n)O(n) Code: