CF1029A Many Equal Substrings（kmp！！！！最通俗易懂的文章模板）

题目描述

You are given a string tt consisting of nn lowercase Latin letters and an integer number kk .

Let's define a substring of some string ss with indices from ll to rr as s[l \dots r]s[l…r] .

Your task is to construct such string ss of minimum possible length that there are exactly kk positions ii such that s[i \dots i + n - 1] = ts[i…i+n−1]=t . In other words, your task is to construct such string ss of minimum possible length that there are exactly kk substrings of ss equal to tt .

It is guaranteed that the answer is always unique.

输入格式

The first line of the input contains two integers nn and kk ( 1 \le n, k \le 501≤n,k≤50 ) — the length of the string tt and the number of substrings.

The second line of the input contains the string tt consisting of exactly nn lowercase Latin letters.

输出格式

Print such string ss of minimum possible length that there are exactly kk substrings of ss equal to tt .

It is guaranteed that the answer is always unique.

题意翻译

题目描述：

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

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

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

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

第二行输入字符串t

输出：

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

输入输出样例

输入  

3 4

aba

输出  

ababababa

输入

3 2

cat

输出

catcat

我们这个题就是找前缀和后缀最大的公共串，然后打印出来，我在代码里面写的很清晰对于kmp模板解析，如果这篇文章点赞量可以的话，我会考虑出一篇kmp算法的精确解析。

#include<bits/stdc++.h>
using namespace std;
int n, k;
char a[100];
int ne[100];
int main()
{
  cin >> n >> k;
  cin >> a + 1;
  for (int i = 2, j = 0;i <= n;i++)
  {
    while (a[j + 1] != a[i] && j)  //j不为0，和这里的意思就是如果 
     j = ne[j];//这里的意思就是跳到 
    if (a[j + 1] == a[i])  
       j++;
    ne[i] = j;//next数组对应的i所在的值。 
  }
  for (int i = 1;i <= n;i++)
  cout << a[i];//输入字符串 因为这里有一个了所以要减1 
  int ans = k - 1;//接几个 
  while (ans--)
    cout << a+1+ne[n];//后面的字符串 //只是最后要最大相同子串直接，看能不能直接接在屁股后面； 
}