51nod-1523 非回文

原题链接

1523 非回文

题目来源：  CodeForces

基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题

一个字符串是非回文的，当且仅当，他只由前p个小写字母构成，而且他不包含长度大于等于2的回文子串。

给出长度为n的非回文串s。请找出字典序比s大的，而且字典序要最小的长度为n的非回文。

Input

单组测试数据。 第一行有两个整数n 和p (1≤n≤1000; 1≤p≤26)。 第二行包含一个字符串s，它的长度是n。输入保证他是非回文的。

Output

输出字典序比s大的且字典序要最小的长度为n的非回文，如果不存在输出NO。

Input示例

样例输入1 3 3 cba 样例输入2 3 4 cba

Output示例

样例输出1 NO 样例输出2 cbd

一个字符串不存在长度为2以及以上的回文子串只要满足str[i] != str[i-1] && str[i] != str[i-2]

#include <bits/stdc++.h>
#define maxn 1005
#define INF 2e15
typedef long long ll;
using namespace std;

char str[maxn];
int main(){
//	freopen("in.txt", "r", stdin);
	int p, n;
	scanf("%d%d", &n, &p);
	scanf("%s", str);
	for(int i = 0; i < n; i++)
	 str[i] -= 'a';
	int sign = -1;
	for(int i = n - 1; i >= 0; i--){
		for(int j = str[i] + 1; j < p; j++){
			if((i < 1 || j != str[i-1]) && (i < 2 || j != str[i-2])){
				sign = i;
				str[i] = j;
				break;
			}
		}
		if(sign != -1)
		 break;
	}
	if(sign == -1){
		puts("NO");
		return 0;
	}
	for(int i = sign+1; i < n; i++){
		for(int j = 0; j < p; j++){
			if((i < 1 || j != str[i-1]) && (i < 2 || j != str[i-2])){
				str[i] = j;
				break;
			}
		}
	}
	for(int i = 0; i < n; i++)
	 str[i] += 'a';
	puts(str);
	return 0;
}