题解 | J

找到第一个合法的去更新，如果这样是需要一直跳的

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,f[N],ne[N];
char s[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>n>>(s+1);
        ne[1]=0;
        for(int i=2,j=0;i<=n;i++){
            while(j&&s[i]!=s[j+1])j=ne[j];
            if(s[i]==s[j+1])j++;
            ne[i]=j;
        }
//         memset(f,0x3f,sizeof f);
        for(int i=1;i<=n;i++)f[i]=1e9;
        f[0]=0;
        for(int i=1;i<=n;i++){
            f[i]=f[i-1]+1;
            int j=i;
            while(ne[j]*2>i)j=ne[j];
            f[i]=min(f[i],f[i-ne[j]]+1);
        }
        cout<<f[n]<<'\n';
    }
}