CF1948D
链接:
题目大意:
给你一个字符串,字符串由小写字母和?组成,?可以变成任何数,问你重复子字符串的最大长度
定义重复子字符串为,任意i都满足s[i] = s[i + len]的子字符串
思路:
- 枚举长度,然后对于每个长度,写一个f表表示是否可以喝i+len处对应,
- 然后找最长连续的f 为 1的长度,判断是否>=len,如果大于等于那么这个len就是可行的,最后找到最大的可行len即可,也可以倒序枚举len,找到符合要求len直接输出
代码:
void solve(){
string s;
cin >> s;
int n = s.size();
s = " " + s;
int f[n + 1];
for(int len = n/2;len >= 1;len--){
memset(f,0,sizeof f);
for(int i = 1;i+len <= n;i++){
if(s[i]==s[i+len]||s[i]=='?'||s[i+len]=='?') f[i] = 1;
}
int cnt = 0;
for(int i = 1;i <= n;i++){
if(f[i] == 1){
cnt++;
if(cnt==len){
cout << len*2 << endl;
return;
}
}else{
cnt = 0;
}
}
}
cout << 0 << endl;
}
时间复杂度
\(O(n^2)\)
标签:CF1948D,int,重复子,len,字符串,长度 From: https://www.cnblogs.com/bananawolf/p/18393609