✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

淘天-2026.04.08-工程岗

三道题整体偏建模，算法本身不复杂，难点在读清题意。第一题是字符串拆分的合法性判定，第二题需要先梳理清楚交换操作所保持的不变量，第三题按值离线处理，逐步统计各元素的贡献。

1. 毛利兰的字符串核查

问题描述

毛利兰在整理一批案件文字记录时，发现某些字符串恰好可以由同一批记录中的另外两条拼接而成。她需要将这类字符串统计出来。

形式化定义：给定一个由非空小写字符串构成的序列，若字符串 满足——存在两个不同下标 ，使得 与 均为非空字符串，且 ——则称下标 对应的字符串为可删去的。

统计每组数据中可删去字符串的下标总数。

输入格式

每个测试文件包含多组测试数据。

• 第一行输入一个整数 ，表示测试组数。
• 对于每组测试数据：
  • 第一行输入一个整数 ，表示字符串数量。
  • 接下来输入 行，每行一个只含小写字母的非空字符串。

输出格式

对于每组测试数据，输出一行一个整数，表示可删去的字符串下标数量。

样例输入

2
5
a
b
ab
abc
bc
4
a
aa
a
aaa

样例输出

2
2

数据范围

• 
• 
• 单个测试文件中，所有测试数据的 之和不超过
• 单个测试文件中，所有字符串长度之和不超过
• 每个字符串只包含小写字母，且长度至少为

样例解释1

第 1 组：ab = a + b，abc = a + bc，共 2 个可删去字符串。

样例解释2

第 2 组：序列中有两个 a，可以拼成 aa；任意一个 a 与 aa 可以拼成 aaa，答案同样为 2。

题解

枚举策略

对目标串 （长度为 ）逐一枚举切分点 ，其中 ，将其拆成前半段 与后半段 ，检查这两个子串是否均在原序列中存在。只要存在某个切分点使两段同时命中， 即为可删去的。

相同下标的处理

当前缀与后缀内容不同时，只需二者均在序列中出现过，必然对应不同位置，无需额外处理。

需要特别考虑的情形是前缀与后缀完全相同——此时要求该字符串在原序列中至少出现两次，才能取到两个不同下标完成拼接。

哈希加速

对每个切分点朴素截取子串并比较，最坏情形下时间复杂度退化为平方级别。题目给定"所有字符串长度之和不超过 "，适合采用前缀哈希（推荐双哈希以降低碰撞概率）处理：

1. 将序列中每个完整字符串的哈希值存入哈希表，同时记录出现次数。
2. 对每个字符串预处理前缀哈希数组。
3. 枚举切分点时，以 时间取得前缀与后缀的哈希值。
4. 在哈希表中查询两段是否存在（若前后缀相同，需检查出现次数是否 ）。

每个字符仅被常数次处理，总体复杂度与输入规模线性相关。

复杂度分析

设所有测试数据的总字符串长度为 。

• 时间复杂度：
• 空间复杂度：

参考代码（Python）

import sys

def read_line():
    return sys.stdin.readline().strip()

def precompute_powers(limit):
    while len(pow_mod1) <= limit:
        pow_mod1.append(pow_mod1[-1] * BASE % MOD1)
        pow_mod2.append(pow_mod2[-1] * BASE % MOD2)

def hash_full(text):
    h1 = h2 = 0
    for ch in text:
        val = ord(ch) - 96
        h1 = (h1 * BASE + val) % MOD1
        h2 = (h2 * BASE + val) % MOD2
    return h1, h2

def prefix_hashes(text):
    length = len(text)
    pref1 = [0] * (length + 1)
    pref2 = [0] * (length + 1)
    for idx, ch in enumerate(text):
        val = ord(ch) - 96
        pref1[idx + 1] = (pref1[idx] * BASE + val) % MOD1
        pref2[idx + 1] = (pref2[idx] * BASE + val) % MOD2
    return pref1, pref2

def segment_hash(pref, start, end, power_list, mod):
    return (pref[end] - pref[start] * power_list[end - start]) % mod

def main():
    batches = int(read_line())
    results = []

    for _ in range(batches):
        count = int(read_line())
        strings = [read_line() for _ in range(count)]
        for s in strings:
            precompute_powers(len(s))

        hash_count = {}
        for text in strings:
            key = (len(text),) + hash_full(text)
            hash_count[key] = hash_count.get(key, 0) + 1

        total = 0
        for text in strings:
            size = len(text)
            if size < 2:
                continue

            pref1, pref2 = prefix_hashes(text)
            valid = False
            for split in range(1, size):
                left_key = (split, pref1[split], pref2[split])
                if hash_count.get(left_key, 0) == 0:
                    continue

                right_len = size - split
                right_h1 = segment_hash(pref1, split, size, pow_mod1, MOD1)
                right_h2 = segment_hash(pref2, split, size, pow_m