T1 word

Description

你有一个由小写字母组成的长度为 $n$ 的字符串。每一步你要找到它的子串中最短的重复块（一个重复块由一个字符串与自身连接而成）。如果有多于一个，你必须选择最左边的那个。你要将那个形如 XX(X - 某个字符串)的重复块替换成 X，即删除其中的一个 X。重复以上步骤直到字符串中不存在重复块。
输出最终的字符串。

Description

给定长度为 $n$ 的字符串 s ，要求构造字符串序列 $s_1,s_2,\cdots,s_k$ ，满足 $\forall i\in[1,k]$ ，$s_i$ 是 s 的子串，且 $\forall i\in[2,k]$， 都有 $s_{i-1}$ 在 $s_i$ 中至少出现了两次（可以有重叠部分）。$s_i$ 不能为空。求最大的 $k$ 值。
$1\leq n\leq 2\times 10^5$

Solution

Description

给定一棵以 $1$ 为根的有 $3n+1$ 个节点的树，树上每个节点均有一个输出端。树上有 $n$ 个节点有 $3$ 个子节点，其余的 $2n+1$ 个节点无子节点（也就是叶子）。$2n+1$ 个节点的初始值均为 $0/1$ ，并且已经提前知道；剩余 $n$ 个节点的值为其 $3$ 个子节点中出现次数最多的值。$q$ 次询问，每次改变一个叶子节点的值，求操作后根节点的值。
$n,q\leq 5\times 10^5$

Solution

Description

给定字符串 s 。有 $q$ 个询问，每个询问形如 $t\ l\ r$ ，表示查询字符串 t 中有多少个本质不同的子串在 s[l:r] 中没出现过。
$q,|s|,|t|\leq 5\times 10^5$

Solution

Description

给定长度为 n 的字符串 s ，对于 s 的每个前缀，求该前缀是否能满足 AB...ABA 的形式，其中 A 恰好有 k+1 个，B 恰好有 k 个 。A B 可以是任意字符串，或者为空串；k 是给定的。
$1\leq n,k\leq 10^6$

Solution

Description

给定长度为 n 的字符串 A 和长度为 m 的字符串 B 。当以 A 为模式串时，你希望求出对于 B 的每一个位置 i ，从该位置开始的连续 n 个字符形成的子串是否能与 A 完全匹配。A B 中可能含有通配符 @ 。通配符可以视作为任意小写字母。
$1\leq n\leq m\leq 3\times 10^5$

Solution

Description

给定一个由 n 个字符串 s 组成的字典，再给定 m 句话 t ，求每句话在该字典下可以理解的最长前缀。
$n\leq 20,m\leq 50,|s|\leq 10,|t|\leq 2\times 10^6$

Solution

Description

给定长度为 n 的字符串 s ，每次只能交换相邻两个位置。求使得 s 为回文串的最小交换次数。无解输出 -1 。
$n\leq 10^6$，保证都是大写字母

Solution

回文自动机（PAM）是针对给定串，包含了该串所有回文子串的信息的自动机。
PAM 的每个节点代表了一个本质不同的回文子串，记 s[p] 为点 p 代表的回文子串。
PAM 的每个节点有三个基础属性：fail/len/child 。
len：a[p].len 表示 s[p] 的长度。

Description

给你一棵 $n$ 个点的树，每个点为黑色或白色。要求维护两个操作：

• 改变点 u 的颜色
阅读全文 »