CF1029A

Many Equal Substrings

题面翻译

题目描述：

你有一个字符串t，它由n个字母组成。

定义一个字符串s的子串为s[l...r]，表示从位置l到r构成的一个新的串。

你的目标是构造一个字符串s，使得它的可能长度最小，要求s中存在k个位置i,可以找到k个以i为出发点的子串t。

输入：第一行输入两个整数n和k，表示t的长度和需要k个子串

第二行输入字符串t

输出：

输出满足条件的长度最小的s。题目保证答案唯一。

题目描述

You are given a string $ t $ consisting of $ n $ lowercase Latin letters and an integer number $ k $ .

Let's define a substring of some string $ s $ with indices from $ l $ to $ r $ as $ s[l r] $ .

Your task is to construct such string $ s $ of minimum possible length that there are exactly $ k $ positions $ i $ such that $ s[i i + n - 1] = t $ . In other words, your task is to construct such string $ s $ of minimum possible length that there are exactly $ k $ substrings of $ s $ equal to $ t $ .

It is guaranteed that the answer is always unique.

输入格式

The first line of the input contains two integers $ n $ and $ k $ ( $ 1 n, k $ ) — the length of the string $ t $ and the number of substrings.

The second line of the input contains the string $ t $ consisting of exactly $ n $ lowercase Latin letters.

输出格式

Print such string $ s $ of minimum possible length that there are exactly $ k $ substrings of $ s $ equal to $ t $ .

It is guaranteed that the answer is always unique.

样例 #1

样例输入 #1

3 4 aba

样例输出 #1

ababababa

样例 #2

样例输入 #2

3 2 cat

样例输出 #2

catcat

看到这道题要求的答案，想到了熟悉的循环节问题，就从这入手吧。还是先求出来$t$的最小的循环节（记作$p$），并根据$k$进行多次构造。

但是，通过样例一可以发现，构造出来的$s$可能不是恰好由整数个$p$构成。看样例一，可以发现最后恰好是由$pmt[n-1]$构成。

根据题意，可以总结出：前面输出$k-1$个循环节，后面输出$t$即可。因为前面的$k-1$个循环节首尾相连，已经是构成了$k-1$个$t$结构了。 ## AC代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
int pmt[MAXN],n,k;
void get_pmt(const string &s){
    for(int i=1,j=0;i<s.length();i++){
        while(j&&s[i]!=s[j])j=pmt[j-1];
        if(s[i]==s[j])j++;
        pmt[i]=j;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    string s;
    cin>>n>>k>>s;
    get_pmt(s);
    for(int i=1;i<=k-1;i++){
        for(int j=0;j<s.length()-pmt[s.length()-1];j++){
            cout<<s[j];
        }
    }
    cout<<s;
    return 0;
}