Codeforces 196 D. The Next Good String

D. The Next Good String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
In problems on strings one often has to find a string with some particular properties. The problem authors were reluctant to waste time on thinking of a name for some string so they called it good. A string is good if it doesn't have palindrome substrings longer than or equal to d.
You are given string s, consisting only of lowercase English letters. Find a good string t with length |s|, consisting of lowercase English letters, which is lexicographically larger than s. Of all such strings string t must be lexicographically minimum.
We will call a non-empty string s[a ... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) a substring of string s = s1s2... s|s|.
A non-empty string s = s1s2... sn is called a palindrome if for all i from 1 to n the following fulfills: si = sn - i + 1. In other words, palindrome read the same in both directions.
String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ... , x|y| = y|y|, or there exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 > yr + 1. Characters in such strings are compared like their ASCII codes.
Input
The first line contains integer d (1 ≤ d ≤ |s|).
The second line contains a non-empty string s, its length is no more than 4·105 characters. The string consists of lowercase English letters.
Output
Print the good string that lexicographically follows s, has the same length and consists of only lowercase English letters. If such string does not exist, print "Impossible"(without the quotes).
Sample test(s)
input

3
aaaaaaa

output

aabbcaa

input

3
zzyzzzz

output

Impossible

input

4
abbabbbabbb

output

abbbcaaabab

검색 +hash,
길이가 L인 캐럿 열에는 길이가 L-2인 캐럿 열이 있어야 합니다.
회문을 판단할 때 d와 d+1이 회문열이 아니라고 판단하면 된다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef unsigned long long int ull;

const int maxn=500100;

char s[maxn],r[maxn];
int n,d;
ull p[maxn],hash[maxn],rhash[maxn];

bool ok(int ed,int d)
{
	ed++;
	int st=ed-d+1;
	if(st<0) return true;
	if((rhash[ed]-rhash[st-1]*p[d])*p[st-1]!=hash[ed]-hash[st-1])
		return true;
	return false;
}

bool dfs(int x,int t)
{
	if(x==n)
	{
		puts(r);
		return true;
	}
	for(r[x]=(t?s[x]:'a');r[x]<='z';r[x]++)
	{
		hash[x+1]=hash[x]+r[x]*p[x];
		rhash[x+1]=rhash[x]*175+r[x];
		if(ok(x,d)&&ok(x,d+1)&&dfs(x+1,t&&(r[x]==s[x])))
			return true;
	}
	return false;
}

int main()
{
	scanf("%d %s",&d,s);
	n=strlen(s);
	int i=n-1;
	for(;i>=0&&s[i]=='z';i--)
		s[i]='a';
	if(i<0)
	{
		puts("Impossible");
		return 0;
	}
	s[i]++;p[0]=1;
	for(int i=1;i<n+100;i++)
		p[i]=p[i-1]*175;
	if(dfs(0,1)==false)
		puts("Impossible");
	return 0;
}