最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • Copy String

    正文概述 陈老师   2026-01-20 15:14:49  

    题目描述

    给定两个长度为 nn 的字符串 ss 和 tt,你希望通过一系列操作将 ss 转换为 tt。

    操作定义如下:

    1. 构造一个新的字符串 s′s',长度为 nn,满足 s1′=s1s'_1 = s_1。
    2. 对于每个 1<i≤n1 < i \le n,可以选择 si′=sis'_i = s_i 或 s′∗i=s∗i−1s'*i = s*{i-1}。
    3. 然后将 ss 替换为 s′s'。

    你的任务是在 尽可能少的操作次数 内完成转换。 你还需要输出每次操作后构造的字符串 s′s'。

    如果无法在不超过 kmaxk_{\text{max}} 次操作内完成转换,输出 -1。


    输入格式

    输入包含多组测试数据。

    第一行输入一个整数 tt:

    1≤t≤1041 \le t \le 10^4

    接下来每组测试包含:

    • 第一行包含两个整数 n,kmaxn, k_{\text{max}}:

    1≤n⋅kmax≤1061 \le n \cdot k_{\text{max}} \le 10^6

    • 第二行包含一个长度为 nn 的字符串 ss。
    • 第三行包含一个长度为 nn 的字符串 tt。

    保证:

    • 所有测试中 ∑n⋅kmax≤106\sum n \cdot k_{\text{max}} \le 10^6
    • 字符串 ss 和 tt 仅包含小写字母。

    输出格式

    对于每组测试:

    • 如果无法在不超过 kmaxk_{\text{max}} 次操作内完成转换,输出一行 -1。
    • 否则,第一行输出一个整数 k≤kmaxk \le k_{\text{max}},表示最少操作次数。 接下来的 kk 行,每行输出一个长度为 nn 的字符串,表示每次操作后得到的 s′s'。

    若存在多种合法解,可输出任意一种。


    样例

    7
    4 1
    abcd
    aabd
    2 2
    ab
    ab
    5 3
    abcde
    abbcc
    9 1
    egcnyeluw
    eegccyelw
    10 3
    vzvylxxmsy
    vvvvvllxxx
    4 6
    acba
    aaac
    5 7
    acabb
    aaaca
    

    1
    aabd
    0
    2
    abbcd
    abbcc
    -1
    3
    vvzvylxxms
    vvvzvllxxm
    vvvvvllxxx
    2
    aacb
    aaac
    2
    aacab
    aaaca
    

    样例解释

    • 样例 1: 显然 ss 可以通过一次操作变为 tt。

    • 样例 2: 初始 s=ts = t,无需操作。

    • 样例 4: 虽然可以在两次操作内将 ss 转换为 tt,但是 kmax=1k_{\text{max}} = 1,所以输出 -1。

    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » Copy String