A50245.午枫的字符串移动 题解

这题有一个很引人注目的点：$n \leq 10^4$。这意味着允许 $O(n^2)$ 算法！

首先考虑到移动 $n$ 次等于不动，所以求得 $0 \leq m<n$。

直接枚举 $m$，然后模拟移动的过程，最后判断是否和 $s'$ 恰好相差 $k$ 字符。

判断可以使用双指针，如果 $s_l=s'_r$，则成功匹配；反之匹配失败，需要在 $s'_r$ 前添加一个字符。统计添加的字符数量是否恰好为 $k$​ 即可。

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,l,r,sum;
char c;
string s,t;
int main(){
    cin>>n>>k>>s>>t;
    for(ll i=0;i<n;i++){
        l=r=sum=0;
        while(l<n&&r<n-k){
            if(s[l]==t[r]) l++,r++;
            else sum++,l++;
        }
        sum+=n-l;
        if(sum==k){
            cout<<i;
            return 0;
        }
        c=s.back();
        for(ll j=n-1;j>=1;j--) s[j]=s[j-1];
        s[0]=c;
    }
    return 0;
}