时间限制：1000MS 内存限制：131072KB
难度：\(4.0\)
输入长度为 \(n\) 的串 \(S\) ，求 \(S\) 的最长双回文子串 \(T\)，即可将 \(T\) 分为两部分 \(X, Y\)（\(\left|X\right|, \left|Y\right| \geq 1\)），且 \(X, Y\) 都是回文串。
一行由小写英文字母组成的字符串 \(S\)。
一行一个整数，表示最长双回文子串的长度。
|
1 |
baacaabbacabb |
|
1 |
12 |
从第二个字符开始的字符串 aacaabbacabb 可分为 aacaa 与 bbacabb 两部分，且两者都是回文串。
对于 \(100\%\) 的数据， \(2 \leq \left|S\right| \leq 10^5\)。
时间限制：2000MS 内存限制：1048576KB
难度：\(7.0\)
在工程的开发中，我们常常用 \(Git\) 进行版本的管理。这个方式具体来说是这样的：刚开始只有一个版本 \(0\)，表示最初始的情况，也就是空的项目；接下来一个用户可以对某一个版本 \(p\) 的项目进行修改，得到一个新的版本 \(i\)。这样，一个工程就产生了许多不同的版本，而管理员可以选择一些优秀的，将其合并到主版本中。
\(F\) 公司有一个项目 \(U\)，这个项目由一个字符串构成。版本 \(0\) 为空串。有 \(n\) 个开发者按顺序对这个项目进行了修改，其中第 \(i\) 个开发者将第 \(p_i ( 0 \le p_i < i)\) 个版本的开头添加上一个字符 \(c_i (1 \le c_i \le m)\) 作为新的版本 \(i\)。
作为项目的总负责人，你希望对这些版本进行评价。对一个字符串 \(S\)，称串 \(S\) 是串 \(T\) 的超前缀，当且仅当串 \(S\) 是串 \(T^{*}\) 的前缀。 \(T^{*}\) 表示 \(T\) 重复无限次得到的一个无限长度的串，如若 \(T = abcd\)，则 \(T^{*} = abcdabcdabcd \cdots\)。我们称串 \(S\) 的 “\(kitty\) 长度” 为 \(l\)，当且仅当存在一个长度为 \(l\) 的串 \(T\) 使得 \(S\) 是 \(T\) 的超前缀，且不存在小于 \(l\) 的串 \(T’\) 使得 \(S\) 是 \(T’\) 的超前缀（定义空串的 \(kitty\) 长度为 \(0\)）。你需要做的就是对每一个版本求出其的 \(kitty\) 长度（设版本 \(i\) 的 \(kitty\) 长度为 \(kitty(i)\)）。
在实际运营中，有两种情况，我们用一个数 \(k \in \{0,1\}\) 表示。在 \(k = 0\) 的情况中， 你可以等候开发者进行所有修改后，再进行计算；但在 \(k = 1\) 的情况中，开发者希望能够实时得到自己修改得到的版本的 \(kitty\) 长度，你需要实时计算出每个版本的 \(kitty\) 长度。
第一行包含三个整数 \(n,m,k\)。
接下来 \(n\) 行，其中第 \(i\) 行包含两个整数 \(p^{′}_{i}; c^{′}_{i}\)，其中：
如果 \(k = 0\) ，则 \(p_i = p^{′}_{i}\)，\(c_i = c^{′}_{i}\)；
时间限制：1000MS 内存限制：262144KB
难度：\(5.5\)
班里有 \(n\) 个同学。老师为他们选了 \(n\) 个笔名。现在要把这些笔名分配给每一个同学， 每一个同学分配到一个笔名，每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为 \(a\)，真名为 \(b\)，则他们之间的相关度为 \(lcp(a,b)\)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。
对于两个字符串 \(a,b\)（从 \(1\) 开始标号），定义 \(a,b\) 的最长公共前缀 \(lcp(a,b)\) 为最大的非负整数 \(k\)，使得 \(k\le |a|, k\le |b|\)，且对所有 \(i=1,2,\ldots,k\)，\(a_i = b_i\) 。
给出一种分配笔名的方案，使得匹配质量最大。
第 \(1\) 行有 \(1\) 个整数 \(n\)，表示班级中同学的数目。接下来 \(n\) 行，表示每一个同学的真名。最后 \(n\) 行是老师已经安排好的笔名。每行的名称仅由小写字母组成。
将分配笔名的方案输出到文件中。第一行输出一个数，表示最大匹配质量。接下来 \(n\) 行，每行两个数 \(a,b\)，表示把编号为 \(b\) 的笔名分配给编号为 \(a\) 的同学。同学和笔名均按输入顺序从 \(1\) 至 \(n\) 编号。若方案不唯一，任意输出一种即可。
|
1 2 3 4 5 6 7 8 9 10 11 |
5 gennady galya boris bill toshik bilbo torin gendalf smaug galadriel |
|
1 2 3 4 5 6 |
11 4 1 2 5 1 3 5 2 3 4 |
对于所有测试点，\(n \leq 100000\)，输入串总长 \(\leq 800000\) 。
时间限制：1000MS 内存限制：65536KB
我们定义两种操作
操作1的格式 ：I 字符串 \(S\)，加入 1 个字符串 \(S\)。
操作2的格式 ：F 字符串\(S\)，查找字符串\(S\)是否在当前寻找前已经出现过
注释：同一个字符串可能多次被插入和查找，字符串长度\(\left|S\right|≤20\)，字符集为小写英文字母。
第一行，指令个数\(N\)。
接下来\(N\)行，每行一个指令。
对于每次查找，找到输出 ‘YES’，没找到输出 ‘NO’ 。
|
1 2 3 4 5 6 7 8 9 10 11 |
10 I abcdef I abcdef F abcdef F abcd I ef F fff F ef F abcdef I asd F assd |
|
1 2 3 4 5 6 |
YES NO NO YES YES NO |
对于 \(40\%\) 的数据 \(N≤5000\)
对于 \(100\%\) 的数据 \(N≤150000\)