SP34020 ADAPET - Ada and Pet 题解

题目链接：SP34020 ADAPET - Ada and Pet

题意：

cxy 刚刚领养了一只新宠物。她正在考虑给它取一个名字。她已经想出了一个漂亮的名字，但现在她觉得这个名字还不够”特别”。她想要找到一个新名字，其中至少包含原始名字作为子串出现 $K$ 次（以强调其重要性）。由于 cxy 不希望宠物的名字太长，她希望找到最短的名字——你能找到它的长度吗？

输入格式：

输入的第一行将包含 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行包含一个非空字符串 $s$，由小写英文字母和数字 $1$ 组成（表示给定名字在新名字中出现的次数）。

所有测试用例中字符串长度的总和不会超过 $5\times 10^5$。

输出格式：

对于每个测试用例，请打印出新名字的最小长度。

结论：最小长度为

$$(n - \mathrm{fail}(n)) \times (k - 1) + n$$

证明么，我们只需要用 $n - \mathrm{fail}(n)$ 的那段在原串后面无限拼就好了，其他方法肯定不会更优。

时间复杂度 $\mathcal{O}(\sum n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

char str[N]; int fail[N];
void solve()
{
    int n,k; cin >> (str + 1) >> k; n = strlen(str + 1);
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && str[j + 1] != str[i]) j = fail[j];
        if(str[j + 1] == str[i]) ++j; fail[i] = j;
    }
    // cout << "fail[n] = " << fail[n] << '\n';
    cout << (n - fail[n]) * (k - 1) + n << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}