题解：P15012 再生

wrz_pussycat296 · 2026-01-24 18:12:37 · 题解

思路

找性质。

我们发现，只要有一个字符在 s 中的位置不同，两个子串 t 就认定不同。

那我们只需找到最近的两个字符，然后左右两边都是两个 t 的公共部分。

设最近两个字符的距离为 d，答案即为 n-d。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[160],d=1e7,c;
string s;
int main(){
    memset(a,-1,sizeof(a));
    cin>>n>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]!='a'&&s[i]!='b')c=1;
        if(a[s[i]]!=-1)d=min(d,i-a[s[i]]);
        a[s[i]]=i;
    }
    if(d==1e7)cout<<-1;
    else cout<<n-d;
}