?

zym2013 · 2025-07-05 23:27:47 · 个人记录

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 检查字符串s是否可以通过插入字符变成t重复k次
bool canBeTransformed(const string& s, int d, int k) {
    int sLen = s.length();
    int tLen = d;
    int targetLen = d * k; // 插入后的长度

    // 确保targetLen >= sLen
    if (targetLen < sLen) {
        return false;
    }

    int sPos = 0; // s中的当前位置

    // 模拟构造t^k并匹配s
    for (int i = 0; i < targetLen; i++) {
        int tPos = i % tLen; // t中的位置

        // 如果s已经匹配完，剩余位置可以任意填充
        if (sPos >= sLen) {
            continue;
        }

        // 如果当前位置可以匹配s中的字符
        if (s[sPos] == ('a' + tPos)) {
            sPos++;
        }
    }

    // 如果s全部匹配成功
    return sPos == sLen;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        string s;
        cin >> n >> s;

        int minLength = n; // 初始化为原长度

        // 遍历所有可能的d
        for (int d = 1; d <= n; d++) {
            // 计算最少需要重复的次数k
            int k = (n + d - 1) / d; // 向上取整

            // 检查是否存在t使得s可以变成t^k
            // 这里我们用t = "abcdefghijklmnopqrstuvwxyz"的前d个字符作为示例
            // 实际应该检查是否存在任意t满足条件
            // 优化：我们可以检查是否存在一个t，使得s是t^k的子序列
            if (canBeTransformed(s, d, k)) {
                minLength = min(minLength, d);
            }
        }

        cout << minLength << endl;
    }

    return 0;
}