程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #265 (Div. 2) C. No to Palindromes!(字符串+構造??)

Codeforces Round #265 (Div. 2) C. No to Palindromes!(字符串+構造??)

編輯：C++入門知識

Codeforces Round #265 (Div. 2) C. No to Palindromes!(字符串+構造??)

C. No to Palindromes! time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Paul hates palindromes. He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and sdoesn't contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string s of length n. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.

Input

The first line contains two space-separated integers: n and p (1?≤?n?≤?1000; 1?≤?p?≤?26). The second line contains string s, consisting of nsmall English letters. It is guaranteed that the string is tolerable (according to the above definition).

Output

If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print "NO" (without the quotes).

Sample test(s) input

3 3
cba

output

NO

input

3 4
cba

output

cbd

input

4 4
abcd

output

abda

Note

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s1?=?t1, ..., si?=?ti, si?+?1?>?ti?+?1.

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.

題意給出一個由字母表的前p個字符構成的長度為n的串,該串的子串中不存在長度大於等於2的回文,要你求下一個字典序比這這個串大且滿足串中不存在長度大於等於2的回文子串的串.(串的長度和原串等長)思路,因為字典序比這個串大,所以只需要增加該串的某個位置,然後這個位置後面的構造字典序最小的字符串,代碼如下

#include
#include
#include
#include
#include
using namespace std;
int n,p;
char s[1005],ans[1005];
int main()
{
    ios_base::sync_with_stdio(false);
    while(cin>>n>>p)
    {
        cin>>s;
        int L=strlen(s);
        bool ok=false;
        for(int j=L-1; j>=0; j--)
        {
            for(int i=1; s[j]+i<'a'+p; i++)
            {
               char tmp=s[j]+i;
               if(j>=2&&(tmp==s[j-1]||tmp==s[j-2]))continue;
               if(j==1&&tmp==s[j-1])continue;
               int k=j+1;
               s[j]=tmp;
               if(j==L-1){ok=true;break;}
               while(k1&&s[k-2]-'a'==c)continue;
                        s[k]=c+'a';
                        if(k==L-1)ok=true;
                        break;
                  }
                  k++;
               }
               if(ok)break;
            }
            if(ok)break;
        }
        if(ok)puts(s);
        else puts("NO");
    }
    return 0;
}