【2024牛客寒假算法基础集训营3】C题KMP解法

起因：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的时候就说明同时满足了。然后两两合并的时候只要保证 $n<m$ ，就不用管交叉的事情，只要短的字符串不交叉，大的肯定不交叉，所以直接让 $i$ 和 $n-i$ 做答案合并就行。这一步可以一开始就交换 $n,m$ 和 $s,t$ 实现。

代码


#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);
}