题干：

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

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


Input单组测试数据。 
第一行有两个整数n 和p (1≤n≤1000; 1≤p≤26)。 
第二行包含一个字符串s，它的长度是n。输入保证他是非回文的。Output输出字典序比s大的且字典序要最小的长度为n的非回文，如果不存在输出NO。Sample Input 
样例输入1
3 3
cba
样例输入2
3 4
cba
Sample Output 
样例输出1
NO
样例输出2
cbd

解题报告：

    首先分析出非回文的标志语句，归纳推出是s[i] ! = s[i-1] && s[i] != s[i-2] ，然后用dfs搜索字典序增大的就可以了。


ac代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int len;	
int n,p;
char s[1000+5],ss[1000+5];//s复制到ss，对s做修改 
bool bk[1000+5];
bool ok() {
	if(s[0]==s[1]) return false;
	for(int i = 2; i<len; i++) {
		if(s[i]==s[i-1]||s[i]==s[i-2]) return false;
	}
	if(strcmp(ss,s)==0) return false;
	return true;
}
bool dfs(int step) {
	if(step>n) return false;
	if(step==n) {
		if(ok() ) {
			printf("%s\n",s);
			return true;
		}
		return false;
	}
	char i;
	bk[step]==1 ? i='a' : i = ss[step];
	bk[step]=1;	
	for(; i<=96+p; i++) {
		if(step>=2) {
			if(i==s[step-1]||i==s[step-2]) continue; 
		}
		else if(step==1) if(i==s[step-1]) continue;
		s[step]=i;//还是直接放在for下面也无所谓？ 
		if(dfs(step+1) ) return true;
	}
	return false;
}
int main()
{
	while(~scanf("%d%d",&n,&p)) {
		memset(s,0,sizeof(s));
		memset(ss,0,sizeof(ss));
		memset(bk,0,sizeof(bk));
		scanf("%s",s);
		strcpy(ss,s);
		len=strlen(s);
		if(!dfs(0) ) {
			printf("NO\n");
		}
	}
	return 0 ;
}

法2：（不用深搜）

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1005;
 
char str[MAXN];
 
int main() {
	int n, p;
	scanf("%d%d%s", &n, &p, str + 1);
	for (int i = n; i >= 1; i--) {
		int x = str[i] - 'a';
		if (x < p - 1) {
			int y = -1;
			for (int j = x + 1; j < p; j++) {
				char c = 'a' + j;
				if (i > 1 && c == str[i - 1]) continue;
				if (i > 2 && c == str[i - 2]) continue; 
				y = j;
				break;
			}
			if (y == -1) continue;
			str[i] = 'a' + y;
			//printf("%d : %c\n", i, 'a' + y);
			if (i == n) {
				puts(str + 1);
				return 0;
			}
			for (int j = i + 1; j <= n; j++) {
				for (int k = 0; k < p; k++) {
					char c = 'a' + k;
					if (j > 1 && c == str[j - 1]) continue;
					if (j > 2 && c == str[j - 2]) continue; 
					str[j] = c;
					break;
				}
			}
			puts(str + 1);
			return 0;
		}
	}
	puts("NO");
	return 0;
}




总结：注意字典序搜索的时候，不能都从 ss[step] 开始，需要有一个bk标记数组，因为第一次用完之后还需要从'a'开始，而不是ss[step]