回文串专题

自用笔记算法

回文串专题

hihocoder 1032(最长回文串)

题目要求

输出最长回文串

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
string s,s1;
int main(){
//	freopen("input.txt","r",stdin);
	int t; cin>>t;
	while(t--){
		cin>>s;
		int len=s.size();
		s1.resize(len*2+2);
		s1[0]='$',s1[1]='#';
		for(int i=0;i<len;i++){
			s1[(1+i)<<1]=s[i];
			s1[(1+i)<<1|1]='#';
		}
		vector<int>p(s1.size(),0);
		int ans=0;
		for(int id=0,i=1;i<s1.size();i++){
			if(p[id]+id>i) p[i]=min(p[2*id-i],p[id]+id-i);
			else p[i]=1;
			while(s1[i+p[i]]==s1[i-p[i]]) ++p[i];
			if(i+p[i]>id+p[id]) id=i;
			ans=max(ans,p[i]);
		}
		cout<<ans-1<<endl;
	}	
	return 0;
}

思路

最长回文串On算法：Manacher算法
算法的核心就在这一句上了：p[i] = min(p[2×id-i], p[id] + id - i);

hihocoder 1149(回文总数变形)

题目要求

输出回文数量 注意aba中的aa也计算在内

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const int mod = 1e5+7;
char s[maxn];
int dp[maxn][maxn];
int len;
int flag=1;
int main(){
//	freopen("input.txt","r",stdin);
	int t; cin>>t;
	while(t--){
		cout<<"Case #"<<flag++<<": ";
		scanf("%s",s);
		len=strlen(s);
		mm(dp,0);
		for(int j=0;j<len;j++){
			dp[j][j]=1;
			for(int i=j-1;i>=0;i--){
				dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;
				if(s[i]==s[j]) dp[i][j]=(dp[i][j]+1+dp[i+1][j-1])%mod;
			}
		}
		cout<<dp[0][len-1]<<endl;
	}
	return 0;
}

思路

dp[i][j]表示区间i-j内的回文数量
dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]
若s[i]==s[j] 需要加上dp[i+1][j-1] 由于aba中的aa也算一种 所以再加1

hihocoder 1323(通过操作变成回文串)

题目要求

给定一个字符串 S ，最少需要几次增删改操作可以把 S 变成一个回文字符串？
一次操作可以在任意位置插入一个字符，或者删除任意一个字符，或者把任意一个字符修改成任意其他字符
S 的长度不超过100, 只包含’A’-‘Z’。
输出最少的修改次数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define maxn 105
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int dp[maxn][maxn];
char s[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%s",s+1);
	int len=strlen(s+1);
	mm(dp,0);
	for(int i=len;i>=1;i--){
		for(int j=i+1;j<=len;j++){
			if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
			else dp[i][j]=min(dp[i+1][j],min(dp[i][j-1],dp[i+1][j-1]))+1;
		}
	}
	printf("%d\n",dp[1][len]);
	return 0;
}

思路

dp[i][j]表示区间i-j变成回文串的最少操作次数
当s[i] == s[j]时有dp[i][j] = dp[i+1][j-1]，这个式子的意思就是当你找到两个字符相等的时候最优的解就是它里面一层的结果即dp[i+1][j-1]（
左边界加1并且有边界减去1），这样从中心往外加下去。当s[i] != s[j]的时候就要考虑增、删、改这三种操作了，仔细分析你会发现其实增和删的操作是
一样的增加一个字符和删除一个字符的效果是一样的这时的递推关系式为 dp[i][j] = min(dp[i+1][j]，dp[i][j-1]，dp[i+1][j-1])；这个递推关系
的意思就是要么增加或删除左边的一个字符，要么增加或删除右边的一个字符，要么修改两边中的一个，就有三种选择，选择其中最优的一种情况就得到了
最后的结果。
注意逆序更新即可

cf round427 D(k阶回文串)

题目要求

定义k阶回文串为本身是回文串 且左边和右边相等 也都是回文串
k阶就是k层 问给定的字符串是几阶回文串

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define maxn 5050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int dp[maxn][maxn];
int ans[maxn],len;
char s[maxn];
void init(){
	for(int i=0;i<len;i++){
		int l=0;
		while(i-l>=0 && i+l<len && s[i-l]==s[i+l]) dp[i-l][i+l]=1,l++;
		l=0;
		while(i-l>=0 && i+1+l<len && s[i-l]==s[i+l+1]) dp[i-l][i+l+1]=1,l++;
	}
}
void solve(){
	for(int t=0;t<len;t++){
		for(int i=0;i+t<len;i++){
			int j=i+t,mid;
	    	if(!dp[i][j]) continue;
	    	if(t%2==0) mid=(i+j)/2-1;
	    	else mid=(i+j)/2;
			if(dp[i][mid] && dp[i][j]) dp[i][j]=max(dp[i][j],dp[i][mid]+1);
			ans[dp[i][j]]++;
		}
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%s",s);
	len=strlen(s);
	mm(dp,0),mm(ans,0);
	init();
	solve();
	for(int i=len-1;i>=1;i--) ans[i]+=ans[i+1];
	for(int i=1;i<=len;i++){
		if(i==1) printf("%d",ans[i]);
		else printf(" %d",ans[i]);
	}
	printf("\n");
	return 0;
}

思路

dp[i][j]表示区间i-j是否是回文串 0表示不是 1表示是
接着枚举间隔和起点 计算出终点和中点 注意mid需要奇偶性判断
如果dp[i][mid]和dp[i][j]都是回文串 那么dp[mid][j]也是回文串且左右相等 满足题意
dp更新k数 该阶数的ans值++
最后由于题意里k阶回文串是包括1到k-1阶回文串的 所以逆序累加输出答案即可

HDU 6103(回文字符累加)

转跳链接
补充思路：题意其实就是回文串的变形 所以枚举mid向两边延伸 由于回文串有偶数和奇数个两种情况 而枚举的mid向两边延伸考虑的是奇数的情况
所以偶数的情况需要再做考虑 向右延伸+1即可 由于本题有和的限制 所以枚举的时候超过限制对头出队 类似与单调队列窗口的滑动

HDU 6156(计算k进制下l-r内的回文数)

转跳链接

总结

回文串问题多用dp解决 多为枚举mid再向两边扩展 扩展的时候再枚举间隔 注意奇偶情况即可

1
2
3
4
5
6
7
8
9
10
//dp[i][j]表示区间内是否有回文串
mm(dp,0);
void init(){
	for(int i=0;i<len;i++){
		int l=0;
		while(i-l>=0 && i+l<len && s[i-l]==s[i+l]) dp[i-l][i+l]=1,l++;
		l=0;
		while(i-l>=0 && i+1+l<len && s[i-l]==s[i+l+1]) dp[i-l][i+l+1]=1,l++;
	}
}

1
2
3
4
5
6
7
8
9
10
//dp[i][j]表示区间内回文串的个数
mm(dp,0);
for(int j=0;j<len;j++){
	dp[j][j]=1;
	for(int i=j-1;i>=0;i--){
		dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
		if(s[i]==s[j]) dp[i][j]+=dp[i+1][j-1];
	}
}
cout<<dp[0][len-1]<<endl;

本文标题:回文串专题

文章作者:Hippopmonkey

发布时间:2017-08-14, 16:14:04

最后更新:2017-08-21, 16:02:53

原始链接:http://xuboming8.github.io/2017/08/14/回文串专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 回文串专题
    1. 1.1. hihocoder 1032(最长回文串)
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. hihocoder 1149(回文总数变形)
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. hihocoder 1323(通过操作变成回文串)
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. cf round427 D(k阶回文串)
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 6103(回文字符累加)
    6. 1.6. HDU 6156(计算k进制下l-r内的回文数)
    7. 1.7. 总结
|