Enjoy It

Codeforces Round #506 (Div. 3) ---A. Many Equal Substrings
http://codeforces.com/contest/1029/problem/AKMP的应用#includ...
扫描右侧二维码阅读全文
25
2018/08

Codeforces Round #506 (Div. 3) ---A. Many Equal Substrings

http://codeforces.com/contest/1029/problem/A
KMP的应用

#include<iostream>
using namespace std;

const int maxn = 50;
int nexts[maxn+5];
int main(int argc, char const *argv[])
{
    /* code */
    int n,m;
    string t;
    cin>>n>>m;
    cin>>t;
    string t_tmp = t+"#";
    int n_tmp = n+1;
    int j = 0,k = -1;
    nexts[0] = -1;
    while(j<n_tmp){
        if(k==-1||t_tmp[j]==t_tmp[k]){
            nexts[++j] = ++k;
        }else{
            k = nexts[k];
        }

    }

    int cnt = nexts[n];
    string n_s = "";
    for(int i=0;i<m;i++){
        if(i==0){
            n_s+=t;
        }else{
            n_s+=t.substr(cnt,n);
        }
    }
    cout<<n_s<<endl;
    return 0;
}
最后修改:2018 年 08 月 25 日 09 : 21 AM
如果觉得我的文章对你有用,请随意赞赏

发表评论