首页 > 代码库 > Codeforces Round #253 (Div. 2) B - Kolya and Tandem Repeat

Codeforces Round #253 (Div. 2) B - Kolya and Tandem Repeat

2024-07-09 00:21:59   222人阅读

本题要考虑字符串本身就存在tandem，

如测试用例

aaaaaaaaabbb

3

输出结果应该是8而不是6，因为字符串本身的tanderm时最长的

故要考虑字符串本身的最大的tanderm和添加k个字符后最大的tanderm

#include <iostream>#include <vector>#include <algorithm>#include <string>#include <set>using namespace std;int maxTandem(string& str){    for(int inteval = str.length()/2; inteval>=0; --inteval){        for(int i = 0 ; i <=str.length()-2*inteval; ++i){            bool flag = false;            for(int j = i,k=i+inteval; j < i+inteval; j++,k++){                if(str[j] != str[k]){                    flag = true;                    break;                }            }            if(!flag) return inteval;        }    }    return 0;}int main(){    string str;    int k;    cin  >> str >> k;    int len = str.length();    if(k>=len){        cout<<((k+len)%2 ? k+len-1:k+len)<<endl;    }else{        int newlen = len+k, startIndex=newlen-newlen/2*2, p =newlen/2;        for( p = newlen/2; p> k;  -- p){            int startIndex=newlen-p*2;            bool flag = false;            for(int i = startIndex, j = startIndex+p;  i < min(len,startIndex+p) && j < len; ++ i, ++ j){                if(str[i] != str[j]){                    flag = true;                    break;                }            }            if(!flag) break;        }        cout<<2*max(p,maxTandem(str))<<endl;    }}
View Code

 本题将上面两个部分合并，即在字符串s后面添加k个‘?’,再对整个字符串搜索

#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;int main(){    string s;    int k;    cin >> s >> k;    int slen = s.length();    s+=string(k,‘?‘);    int len = s.length()/2, interval = len;    for(interval = len; interval >=0; interval--){                                      bool flag = false;        for(int p = 0; p<= s.length()-2*interval; ++ p){            flag = false;            for(int i = p, j = p+interval; i < min(slen,p+interval) && j < slen; ++ i, ++ j){                if(s[j]!= ‘?‘ && s[i]!=s[j] ){ flag = true;break;}            }            if(!flag) break;        }        if(!flag) break;    }    cout<<2*interval<<endl;}

 


联系
我们