编译时期常量数组及常用操作

文中所有的代码均遵循C++11的标准并编译通过。

const_array 的实现

在 C++11 标准中的使用constexpr修饰的函数的要求比较严格,只允许在函数体内有一个return语句。那么在这样的限制下,很多的表达式就只能使用递归来完成。

#include <iostream>

#include <cstddef>

template<typename T>

using Invoke = typename T::type;

template<size_t...>

struct index_sequence {

using......

Two Ways Algorithm

Two Ways Algorithm 是一个用于字符串匹配的算法,算法类似 KMP 会返回所有 pattern 出现在 text 里的位置。但是和 KMP 不同的是 two ways algorithm 只使用常数大小的额外空间。

算法使用 \(O(m)\) 的时间预处理,并且可以在 \(O(n)\) 时间完成匹配,在最差的情况下会遍历 text 串两次。

算法细节

模式串 \(x\) 被分成两个部分,\(x_l\) 和 \(x_r\)。在匹配的过程中先从左向右匹配 \(x_r\),如果没有失配再从右向左匹配 \(x_l\)。

所以算法的关键就在于怎么找到一个合理的划......

2015多校Contest 5. 1003. Hotaru's problem

题目大意

一个N-sequence由三个部分组成,并符合:

第一部分和第三部分相同。

第一部分和第二部分回文。

求最长的N-sequence的长度。

分析

N-sequence的特征是第一部分和第三部分相同,并且第一部分和第二部分回文。那么条件可以转化成:第一部分和第二部分 回文,并且第二部分和第三部分 回文。那么问题就转化成了:两个回文串的重合问题。

先用manacher求出任意一个位置作中心的最长回文串的长度。因为第一部分和第二部分组成的回文串s1一定是一个偶数长度的串,所以一定是我们添加的#位置。每个中间位置i可以覆盖左边的i-rad[i]到右边的i+rad[i]的范围......