LightOJ 1258 Making Huge Palindromes（KMP）

题意

给定一个字符串 \(S\) ，一次操作可以在这个字符串的右边增加任意一个字符。求操作之后的最短字符串，满足操作结束后的字符串是回文。

\(1 \leq |S| \leq 10^6\)

思路

\(\text{KMP}\) 的 \(fail\) 数组是整个算法最重要的东西，能拓展出很多东西。

对于一个模式串（pattern）\(P\) ，\(fail\) 数组为 \(f\) ，那么 \(f[i]\) 就是如果匹配到 \(i\) 这个位置失配，下次去尝试的位置，也就说明了从字符串头到 \(f[i]-1\) 这一段，在 \(i-1\) 位置以左有一段相同的串。这是对 \(fail\) 数组的一种理解，想要更深入的理解，最好的方法就是做题。

本题等价于在 \(S\) 左边删去任意字符使剩下的字符串回文，只需求出字符串 \(S\) 从右开始能得到最长的回文串长度即可。设模式串为 \(S\) 的反字符串 \(P\)，回文串长度就是 \(S\) 在最右端能匹配 \(P\) 的最长长度。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

typedef long long LL;

using namespace std;

const int N=1e6+5;

char T[N],P[N];

int n,f[N];

int main()

{

	int Case;

	scanf("%d",&Case);

	FOR(cas,1,Case)

	{

		scanf("%s",T);

		n=strlen(T);

		FOR(i,0,n-1)P[i]=T[n-i-1];

		P[n]='\0';

		f[0]=f[1]=0;

		FOR(i,1,n-1)

		{

			int j=f[i];

			while(j&&P[i]!=P[j])j=f[j];

			f[i+1]=j+(P[i]==P[j]);

		}

		int j=0;

		FOR(i,0,n-1)

		{

			while(j&&T[i]!=P[j])j=f[j];

			if(T[i]==P[j])j++;

			if(i==n-1)printf("Case %d: %d\n",cas,n+(n-j));

		}

	}

	return 0;

}

巴特西

LightOJ 1258 Making Huge Palindromes（KMP）

题意

思路

代码

最新文章

热门文章