Codeforces 1163D Mysterious Code

Codeforces 1163D Mysterious Code

题目链接

https://codeforces.com/contest/1163/problem/D

题目大意

给你一个字符串 $c$ ,你可以将其中的 ‘*’ 换成任意的字符,你需要最大化字符串 $s$ 和 $t$ 在其中出现的次数的差值。

题目分析

这题比较明显是个 $KMP + DP$ 的题。定义 $f[i][j][k]$ 为到第 $i$ 个字符,匹配到 $s_j$ 和 $t_k$ 的最大差值为多少,那么可以从这个歌状态转移到添加完新的字符后在 $KMP$ 上的新的位置,加入匹配上的话需要根据情况 $+1$ 或者 $-1$ 。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

int inf = 0x3f3f3f3f;

int n, m, t;

string a, b, str;

int na[55];
int nb[55];

int f[1005][55][55];

int read(){
	int x;
	scanf("%d", &x);
	return x;
}

int getnext(){
	int i, j;
	
	na[0] = 0;
	na[1] = 0;
	
	for(i=2;i<=n;i++){
		j = na[i - 1];
		while(j and a[j + 1] != a[i]){
			j = na[j];
		}
		
		if(a[j + 1] == a[i]){
			na[i] = j + 1;
		}else{
			na[i] = 0;
		}
	}
	
	nb[0] = 0;
	nb[1] = 0;
	
	for(i=2;i<=m;i++){
		j = nb[i - 1];
		while(j and b[j + 1] != b[i]){
			j = nb[j];
		}
		
		if(b[j + 1] == b[i]){
			nb[i] = j + 1;
		}else{
			nb[i] = 0;
		}
	}
		
	return 0;
}

int main(){
	int i, j, k, l;
	int x, y;
	
	cin >> str >> a >> b;
	
	n = a.length();
	m = b.length();
	
	a = '0' + a;
	b = '0' + b;
	
	str = '0' + str;
	
	getnext();
	
	for(i=0;i<=str.length();i++){
		for(j=0;j<=n;j++){
			for(k=0;k<=m;k++){
				f[i][j][k] = -inf;
			}
		}
	}
	
	f[0][0][0] = 0;
	
	for(i=1;i<str.length();i++){
		for(j=0;j<n;j++){
			for(k=0;k<m;k++){
				if(str[i] != '*'){
					int tmp = f[i - 1][j][k];
					x = j, y = k;
					bool flag = false;
					if(str[i] == a[x + 1]){
						if(x + 1 == n){
							tmp++;
							x = na[x + 1];
							flag = true;
						}
					}else{
						x = na[x];
						while(x and str[i] != a[x + 1]){
							x = na[x];
						}
					}
					if(!flag and str[i] == a[x + 1]){
						x++;
					}
					
					flag = false;
					if(str[i] == b[y + 1]){
						if(y + 1 == m){
							tmp--;
							y = nb[y + 1];
							flag = true;
						}
					}else{
						y = nb[y];
						while(y and str[i] != b[y + 1]){
							y = nb[y];
						}
					}
					if(!flag and str[i] == b[y + 1]){
						y++;
					}
					
					f[i][x][y] = max(f[i][x][y], tmp);
				}else{
					for(l=0;l<26;l++){
						int tmp = f[i - 1][j][k];
						x = j, y = k;
						bool flag = false;
						if('a' + l == a[x + 1]){
							if(x + 1 == n){
								tmp++;
								x = na[x + 1];
								flag = true;
							}
						}else{
							x = na[x];
							while(x and 'a' + l != a[x + 1]){
								x = na[x];
							}
						}
						if(!flag and 'a' + l == a[x + 1]){
							x++;
						}
						
						flag = false;
						if('a' + l == b[y + 1]){
							if(y + 1 == m){
								tmp--;
								y = nb[y + 1];
								flag = true;
							}
						}else{
							y = nb[y];
							while(y and 'a' + l != b[y + 1]){
								y = nb[y];
							}
						}
						if(!flag and 'a' + l == b[y + 1]){
							y++;
						}
						
						f[i][x][y] = max(f[i][x][y], tmp);
					}
				}
			}
		}
	}
	
	int ans = -inf;
	
	for(j=0;j<n;j++){
		for(k=0;k<m;k++){
			ans = max(ans, f[str.length() - 1][j][k]);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据