【题解】CF196D (哈希)

题解：CF196D

前言

感谢老铁送来的字符串，把我创飞了。

题目链接：

洛谷

codeforces

题意：

给定长度为 $n$ 的小写字母串 $s$ 和正整数 $d$。

定义一个串是好的当且仅当他没有长度大于等于 $d$ 的回文子串。

请你求出长度为 $n$ 并且字典序比 $s$ 严格大的好串里，字典序最小的那个。没有输出 Impossible。.

$1\le d\le n\le 4\times 10^5$

分析

显然，我们只需要解决长度为 $d$ 和 $d+1$ 的回文字串，因为长度为 $d+2$ 的回文子串包含长度为 $d$ 的，长度为 $d+3$ 的回文子串包含长度为 $d+1$ 的 $\dots$

考虑如何判断回文串，这里给出 哈希 的方法。

如果我们能在 $O(1)$ 的时间算出 $s_l{s}_{l+1}\dots s_r$ 的哈希值并在 $O(1)$ 的时间算出 $s_r{s}_{r-1}\dots s_l$ 的哈希值，那么我们可以暴力找到第一个不合法的位置，即存在长度为 $d$ 或 $d+1$ 的回文子串的最后一个字符的位置，枚举将它改成哪一个字符能合法，后面一样枚举即可。

对于前者，显然是哈希的板子，对于后者，这也是个套路，我们可以构造 $har(s)={\sum }_{i=0}^{n}bas{e}^i{s}_i$，这样有个好处就是我们还是可以 动态 地从左往右处理这个哈希值。

最后讲一下判断，我们还是按照板子处理 $hal$，最后判断时看一下 $ha{r}_r-ha{r}_{l-1}$ 和 $(ha{l}_r-ha{l}_{l-1}\times bas{e}^{r-l+1})\times bas{e}^{l-1}$ 是否相等即可。这个读者可以自己手推一下。

代码

#include<bits/stdc++.h>
#define ll long long
#define psb push_back
using namespace std;
const int N=4e5+1;
const int base=1331,mod=1e9+9;
ll hal[N],har[N],qha[N];
int m,n;
string s;
bool check(ll l,ll r){
// 判断ll zz=(hal[r]-hal[l-1]*qha[r-l+1]%mod)*qha[l-1]%mod;zz=(zz%mod+mod)%mod;ll fz=har[r]-har[l-1];fz=(fz%mod+mod)%mod;
//	cout<<l<<" "<<r<<" "<<zz<<" "<<fz<<"\n";return zz==fz;
}
signed main(){ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);cin>>m;m--;cin>>s;qha[0]=1;for(int i=1;i<N;i++)qha[i]=qha[i-1]*base%mod;n=s.size();s=" "+s;int id=n;for(int i=1;i<=n;i++){hal[i]=hal[i-1]*base%mod+(s[i]-'a');har[i]=har[i-1]+(s[i]-'a')*qha[i-1]%mod;hal[i]%=mod,har[i]%=mod;if(i>m)if(check(i-m,i)){id=i;break;}if(i>m+1)if(check(i-m-1,i)){id=i;break;}}bool ok=0;for(int i=id;i;i--){for(char c=s[i]+1;c<='z';c++){hal[i]=hal[i-1]*base%mod+(c-'a');har[i]=har[i-1]+(c-'a')*qha[i-1]%mod;hal[i]%=mod,har[i]%=mod;if(i>m&&check(i-m,i))continue;if(i>m+1&&check(i-m-1,i))continue;ok=1;id=i;s[i]=c;break;}if(ok)break;}if(!ok){cout<<"Impossible\n";return 0;}for(int i=id+1;i<=n;i++){for(char c='a';c<='z';c++){hal[i]=hal[i-1]*base%mod+(c-'a');har[i]=har[i-1]+(c-'a')*qha[i-1]%mod;hal[i]%=mod,har[i]%=mod;if(i>m&&check(i-m,i))continue;if(i>m+1&&check(i-m-1,i))continue;s[i]=c;break;}}//cout<<id<<" ";for(int i=1;i<=n;i++)cout<<s[i];return 0;
}