起因： https://zhuanlan.zhihu.com/p/681953843
题解里面虽然提了一嘴能用KMP做，但是我只是知道能求回文border这个结论，实际上我没写过。原因是它虽然能求，但是它求这玩意很麻烦，来回倒腾好几手，做题的时候不如直接上回文机之类的东西了。
为什么kmp可以求回文
正常来讲，kmp是不能求回文的（z-function即exkmp正常来讲也不能求回文），但是这道题把字符串固定在前缀/后缀了，导致上述算法在转化后变得都能求回文了。
border
对于形如abcdxxxxxxabcd的字符串，子串abcd同时出现在了字符串的开头和结尾的位置。它既是一个前缀也是一个后缀。
KMP预处理出next[n]的值就是原串非自身最长border的长度。
border树
考虑这么一个字符串aabaxxxxxaaba
所以从next[n]一路遍历next[n]、next[next[n]]、next[next[next[n]]]...
就能得到原串所有的border。
KMP求回文前缀/后缀
考虑一个字符串xxx......,我们在它的末尾加上一个不在字符串中出现的字符，假设是&，然后再后面添加上它的反串变为xxx......&......xxx，如果xxx是一个回文，那它必定是字符串的一个border。所以遍历新构造字符串的border树就能得到一个字符串所有回文前缀的长度。同理一开始就反过来能得到一个字符串所有回文后缀的长度。
所以这个题只要分别构造如下六个串就可以解决问题。其中带'表示反串。
S&S'
T'&T
S&T
T&T'
S'&S
T&S
如何优雅的实现
问题最终转化成有6条border链，三三分组求交集，然后两两合并。考虑三个限制条件（前缀是回文、后缀是回文、前后缀匹配）其实是互相独立的，没有什么关系，所以可以开一个cnt数组记一下当且位置满足了几个条件，每满足一个就cnt++，当cnt=3的时候就说明同时满足了。然后两两合并的时候只要保证，就不用管交叉的事情，只要短的字符串不交叉，大的肯定不交叉，所以直接让
和
做答案合并就行。这一步可以一开始就交换
和
实现。
代码
#include <bits/stdc++.h>
namespace chino
{
class kmpWrapper
{
private:
std::vector<char> _t;
std::vector<int> _fail;
size_t _l{};
public:
const int &get(size_t idx)
{
return _fail[idx];
}
kmpWrapper()
{
}
/**
* @description: 根据模式串t，预处理kmp的失配数组。
* @param {string} &t 模式串
* @return {*}
*/
kmpWrapper(const std::string &t)
{
_l = t.size();
_fail.resize(_l + 1);
_t.resize(_l + 1);
memcpy(_t.data(), t.c_str(), _l + 1);
_fail[0] = _fail[1] = 0;
for (auto i = 1; i < _l; ++i)
{
auto j = _fail[i];
while (j && _t[i] != _t[j])
{
j = _fail[j];
}
_fail[i + 1] = _t[j] == _t[i] ? j + 1 : 0;
}
}
/**
* @description: KMP字符串匹配
* @param {string} &s 文本串s
* @param {function<int(int begin, int end, int &state)>} &onMatch 外部通知回调函数
* @note 匹配到的位置为[begin,end)左开右闭，下标从0开始，state为状态机状态，通知时为|t|，可主动清零表示继续匹配不重叠，回调返回非0时立即结束。
* @return {*}
*/
void match(const std::string &s,
const std::function<int(int begin, int end, int &state)> &onMatch)
{
match(s.c_str(), onMatch);
}
/**
* @description: KMP字符串匹配
* @param {string} &s 文本串s
* @param {function<int(int begin, int end, int &state)>} &onMatch 外部通知回调函数
* @note 匹配到的位置为[begin,end)左开右闭，下标从0开始，state为状态机状态，通知时为|t|，可主动清零表示继续匹配不重叠，回调返回非0时立即结束。
* @return {*}
*/
void match(const char *s,
const std::function<int(int begin, int end, int &state)> &onMatch)
{
int j = 0;
auto l = strlen(s);
for (int i = 0; i < l; ++i)
{
while (j && s[i] != _t[j])
j = _fail[j];
if (s[i] == _t[j])
++j;
if (j == _l)
{
if (onMatch(i - _l + 1, i + 1, j))
{
return;
}
}
}
}
/**
* @description: 枚举所有不包括本身的border，并进行回调。
* @param {function<int(int border)>} onBorder
* @param {int} begin 默认遍历整串的所有border，如果需要从某个位置开始爬，begin填入下标[0,len)。
* @note 注意，通知中的border代表长度，它对应字符串前缀的下标需要减1。
* @return {*}
*/
void travel(std::function<int(int border)> onBorder,
int begin = -1)
{
if (begin < 0)
{
begin = _l - 1;
}
begin++;
while (begin)
{
begin = _fail[begin];
if (begin && onBorder(begin))
{
return;
}
}
}
};
}
using namespace std;
///------------------ c++ -------------------
void read(int &x)
{
scanf("%d", &x);
}
void read(long long &x)
{
scanf("%lld", &x);
}
void read(char *x)
{
scanf("%s", x);
}
void print(const int &x)
{
printf("%d", x);
}
void print(const long long &x)
{
printf("%lld", x);
}
void print(const char *x)
{
printf("%s", x);
}
///------------------ c++11 -------------------
template <typename T, std::size_t N>
struct _vec : public _vec<std::vector<T>, N - 1>
{
};
template <typename T>
struct _vec<T, 0>
{
using type = T;
};
template <typename T, std::size_t N>
using vec_t = typename _vec<T, N>::type;
template <typename T>
vec_t<T, 0> vec_t_create(const T &data)
{
return data;
}
template <typename T, size_t arg0, size_t... args>
vec_t<T, sizeof...(args) + 1> vec_t_create(const T &data)
{
return vec_t<T, sizeof...(args) + 1>(arg0, vec_t_create<T, args...>(data));
}
template <typename T>
void vread(T *begin, T *end)
{
for (T *i = begin; i != end; ++i)
{
read(*i);
}
}
void read()
{
}
template <typename T, typename... Args>
void read(T &&arg0, Args &&...args)
{
read(arg0);
read(args...);
}
void println()
{
}
template <typename T, typename... Args>
void println(T &&arg0, Args &&...args)
{
print(arg0);
if (sizeof...(args))
{
printf(" ");
println(args...);
}
else
{
printf("\n");
}
}
//-----------------------------------------
int main(int argc, char const *argv[])
{
int n, m;
read(n, m);
vec_t<char, 1> s(n + 1);
vec_t<char, 1> si(n + 1);
vec_t<char, 1> t(m + 1);
vec_t<char, 1> ti(m + 1);
read(s.data());
read(t.data());
memcpy(si.data(), s.data(), n);
reverse(si.data(), si.data() + n);
memcpy(ti.data(), t.data(), m);
reverse(ti.data(), ti.data() + m);
if (n > m)
{
swap(n, m);
swap(s, t);
swap(si, ti);
}
chino::kmpWrapper k[6];
k[0] = chino::kmpWrapper(string(s.data()) + "&" + string(si.data()));
k[1] = chino::kmpWrapper(string(ti.data()) + "&" + string(t.data()));
k[2] = chino::kmpWrapper(string(s.data()) + "&" + string(t.data()));
k[3] = chino::kmpWrapper(string(t.data()) + "&" + string(ti.data()));
k[4] = chino::kmpWrapper(string(si.data()) + "&" + string(s.data()));
k[5] = chino::kmpWrapper(string(t.data()) + "&" + string(s.data()));
vec_t<int, 1> cnt_s(n + 1);
vec_t<int, 1> cnt_t(m + 1);
function<int(int)> callback_s = [&](int border) -> int
{
if (border <= n)
{
cnt_s[border]++;
}
return 0;
};
function<int(int)> callback_t = [&](int border) -> int
{
if (border <= m)
{
cnt_t[border]++;
}
return 0;
};
for (int i = 0; i < 6; ++i)
{
k[i].travel(i < 3 ? callback_s : callback_t);
}
int ans = -1;
for (int i = 1; i <= m; ++i)
{
cnt_t[i] = cnt_t[i] == 3 ? i : cnt_t[i - 1];
}
for (int i = 1; i < n; ++i)
{
if (cnt_s[i] == 3 && cnt_t[n - i])
{
ans = max(ans, i + cnt_t[n - i]);
}
}
println(ans == -1 ? ans : ans << 1);
}
京公网安备 11010502036488号