CodeForces - 1029A Many Equal Substrings

喜欢ヅ旅行 2022-04-16 04:20 214阅读 0赞

## 原题目链接[CodeForces - 1029A][] ##

--------------------

## 分类 ##

CodeForces KMP

--------------------

## 题意 ##

这题是给一个长度为n的字符串 要拼成一个新串使得原来的串在新串中出现k次，用kmp预处理一下首尾的相同前后缀长度，然后就行了

Sample Input

3 4
    aba
    3 2
    cat

Sample Output

ababababa
    catcat

--------------------

## 代码 ##

31ms

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/4 */
    #include <iostream>
    #include <algorithm>
    #include <string.h>
    #include <stdio.h>
    using namespace std;
    const int maxn = 111;
    
    char s[maxn];
    int next[maxn];
    void getNext()
    { 
        int len = strlen(s);
        int j = 0, k = -1;
        next[0] = -1;
        while (j < len)
        { 
            if (k == -1 || s[j] == s[k])
            { 
                j++;
                k++;
                next[j] = k;
            }
            else
            { 
                k = next[k];
            }
        }
    }
    int main()
    { 
        int n, k;
        scanf("%d %d", &n, &k);
        scanf("%s", s);
        getNext();
        int cnt = next[n];
        if (cnt == 0)
        { 
            for (int i = 0; i < k; i++)
            { 
                printf("%s", s);
            }
            printf("\n");
        }
        else
        { 
            printf("%s", s);
            for (int i = 0; i < k - 1; i++)
            { 
                printf("%s", s + cnt);
            }
            printf("\n");
        }
        system("pause");
        return 0;
    }

[CodeForces - 1029A]: https://cn.vjudge.net/problem/1825467/origin

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关 CodeForces1214A

[CodeForces1214A][] 说起来你们可能不信,这题硬生生卡了我\\(1h\\),我想了背包,扩欧,二分....等等一坨办法.结果最后还是用了\\(bfs\\)

系统管理员/ 2023年06月02日 11:58/ 0 赞/ 75 阅读

相关 codeforces 700A

codeforces 700A [http://codeforces.com/contest/700/problem/A][http_codeforces.com_con

刺骨的言语ヽ痛彻心扉/ 2022年09月24日 05:30/ 0 赞/ 210 阅读

相关区间/Multiset-Codeforces 1029C Maximal Intersection

区间/Multiset-Codeforces 1029C Maximal Intersection -------------------- 题目链接：

落日映苍穹つ/ 2022年05月15日 10:08/ 0 赞/ 233 阅读

相关 Codeforces 1029B-Creating the Contest

Codeforces 1029B-Creating the Contest -------------------- 题目链接： [B. Creat

曾经终败给现在/ 2022年05月15日 07:16/ 0 赞/ 158 阅读

相关 KMP-Codeforces 1029A-Many Equal Substrings

KMP-Codeforces 1029A-Many Equal Substrings -------------------- 题目链接： [A. M

拼搏现实的明天。/ 2022年05月15日 07:16/ 0 赞/ 227 阅读

相关 Codeforces 1029D：Concatenated Multiples

[题目传送门][Link 1] 代码： include<bits/stdc++.h> using namespace std; type

柔光的暖阳◎/ 2022年05月14日 02:09/ 0 赞/ 197 阅读

相关 CodeForces - 1029A Many Equal Substrings

原题目链接[CodeForces - 1029A][] -------------------- 分类 CodeForces KMP -------------

喜欢ヅ旅行/ 2022年04月16日 04:20/ 0 赞/ 215 阅读

相关 HDU 5707 Many Equal Substrings

原题目链接[HDU5707][] -------------------- 分类 CodeForces KMP -------------------- 题

清疚/ 2022年04月16日 04:19/ 0 赞/ 211 阅读

相关 PAT A1029

![clipboard.png][] 起先自己想尝试性的直接排序找中位数，内存直接超限；其实这道题可以采用归并排序的思路来做：但是示例依旧白给。。。不过还是展现了

﹏ヽ暗。殇╰゛Y/ 2022年03月07日 10:24/ 0 赞/ 255 阅读

相关 PAT A1029 TwoPointers解法

一、题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

拼搏现实的明天。/ 2022年02月21日 01:47/ 0 赞/ 238 阅读