官方题解

T3 午枫的字符串移动

题目大意

给定原串和最终串，最终串是通过原串循环右移且丢失若干字符得到的，求出原串最小的循环右移次数。

题解思路

由于 $n$ 最大是 $10000$ ，我们可以考虑 $O(n^2)$ 的做法。

首先，很容易发现 $m$ 最大可能是 $n-1$ ，所以我们可以通过枚举 $s'$ 对应原串 $s$ 的开头位置，类比做了 $C(s,m)$ 的操作，一位一位进行比较判断，如果某一位不匹配，那么就让 $s$ 的下一位去匹配，如果 $s$ 的每一位都判断过了还没有匹配到 $s'$ 的最后一位，那么说明不存在这么一个 $m$ 让 $s$ 变成 $s'$ 。

我们只要找到最小的 $m$ 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int INF = 1e18+10;

void solve(){
    int n,k;cin>>n>>k;
    int m=n-k;
    string s,t;cin>>s>>t;

    int res=INF;
    for(int i=0;i<n;i++){
        int l=i,r=0;
        int cnt=0;
        for(int j=0;j<n;j++){
            if(s[l]!=t[r]){
                cnt++;
                l++;
            }
            else{
                l++;
                r++;
            }

            if(r==m) break;
            l%=n;
        }
        if(cnt<=k) res=min(res,(n-i)%n);
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}