\(\text{Problem}\)

\(\text{Solution}\)

最优解一定是一个回文子串的最优构造加上剩下的逐个填入

考虑用回文树建出所有的回文串，然后 \(dp\) 求回文子串最优的构造方案

维护一个 \(\text{half}\) 意义同 \(\text{fail}\)，但要保证长度不超过 \(len\) 的一半且最大

暴力跳 \(\text{fail}\) 发现不行

加上一个小 \(\text{trick}\)：倒着做，用 \(x\) 的 \(\text{half}\) 更新 \(\text{fail[x]}\) 的 \(\text{half}\)

正确性显然

\(\text{Code}\)

#include <cstdio>

#include <cstring>

#include <iostream>

#define re register

using namespace std;

const int N = 1e5 + 5;

int T, Len;

char str[N];

struct PAM{

	int size, last, tot, tr[N][26], fail[N], half[N], len[N], f[N], fa[N];

	char s[N];

	inline int Node(int l)

	{

		++size, memset(tr[size], 0, sizeof tr[size]);

		len[size] = l, fail[size] = half[size] = 0;

		return size;

	}

	inline void clear()

	{

		size = -1, s[last = tot = 0] = '$';

		Node(0), Node(-1), fail[0] = 1;

		memset(f, 0, sizeof f), f[0] = 1;

	}

	inline int getfail(int x)

	{

		while (s[tot - len[x] - 1] != s[tot]) x = fail[x];

		return x;

	}

	inline void insert(char c)

	{

		s[++tot] = c;

		int cur = getfail(last), ch = c - 'a';

		if (!tr[cur][ch])

		{

			int u = Node(len[cur] + 2);

			fail[u] = tr[getfail(fail[cur])][ch], fa[u] = cur, tr[cur][ch] = u;

		}

		last = tr[cur][ch];

	}

	inline void gethalf()

	{

		for(re int i = 2; i <= size; i++) half[i] = fail[i];

		for(re int i = size; i >= 2; i--)

		{

			while ((len[half[i]] << 1) > len[i]) half[i] = fail[half[i]];

			if (len[half[i]] < len[half[fail[i]]]) half[fail[i]] = half[i];

		}

	}

	inline int dp()

	{

		int ans = Len;

		for(re int i = 2; i <= size; i++)

		{

			if (len[i] & 1) f[i] = min(f[fa[i]] + 2, f[fail[i]] + len[i] - len[fail[i]]);

			else f[i] = min(f[fa[i]] + 1, f[half[i]] + (len[i] >> 1) - len[half[i]] + 1);

			ans = min(ans, f[i] + Len - len[i]);

		}

		return ans;

	}

}P;

int main()

{

	scanf("%d", &T);

	for(; T; --T)

	{

		P.clear();

		scanf("%s", str + 1);

		Len = strlen(str + 1);

		for(re int i = 1; i <= Len; i++) P.insert(str[i]);

		P.gethalf();

		printf("%d\n", P.dp());

	}

}

巴特西

JZOJ 4752.字符串合成

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章