CodeForce[1500-2000]——1950E Nearly Shortest Repeating Substring

本文主要是介绍CodeForce[1500-2000]——1950E Nearly Shortest Repeating Substring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

codeforces刷题日记

题目大意：给你一个长度为n的字符串s，要寻找一个长度最小的字符串k，能够让字符串k进行1或多次的拼接，让拼接成的字符串和字符串s长度相等，且至多一个字母不一样。求k的最小长度。

思路：从1到n遍历k的长度i，如果i整除，就跳过，这时s被分成了n/i段，取出第一段和最后一段。如果这两段相等，那其他段必定和这两段一样（不一样的值字母允许存在一个），才符合条件。要是这两段不一样，那其他段（包括两段中的另一段）必然和两段其中一个一样。

#include<bits/stdc++.h>
using namespace std;
int n;string s;
int main(){int t;cin>>t;while(t--){cin>>n>>s;int ans=n;for(int i=1;i<=n;i++){if(n%i) continue;int cnt=0;int flag=1;string ss=s.substr(0,i);for(int j=0;j<n;j++){if(s[j]==ss[j%i]) continue;cnt++;if(cnt>1) {flag=0;break;}}if(flag){ans=min(ans,i);break;}ss=s.substr(n-i,i);cnt=0;flag=1;for(int j=0;j<n;j++){if(ss[j%i]==s[j]) continue;cnt++;if(cnt>1) {flag=0;break;}}if(flag){ans=min(ans,i);break;}}cout<<ans<<endl;} return 0;
}

这篇关于CodeForce[1500-2000]——1950E Nearly Shortest Repeating Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---