ABC-398-F - ABCBA（上字符串哈希） · znzryb

## 思路讲解

和这道leetcode很像

[https://leetcode.cn/problems/shortest-palindrome/solutions/392676/shou-hua-tu-jie-cong-jian-dan-de-bao-li-fa-xiang-d/](https://leetcode.cn/problems/shortest-palindrome/solutions/392676/shou-hua-tu-jie-cong-jian-dan-de-bao-li-fa-xiang-d/)

其实思路也很简单，暴力方法时间复杂度最大的部分其实是一个一个判断字符串是不是回文（一样），那么我们直接用字符串哈希加速这个过程就行。

这个下面的讲的很详细

[P10469 后缀数组(如何算子串哈希值)](/2025/01/15/20250115-220656e5) 

唉，前面怎么样都不太对，结果发现其实是我的哈希递推式子错了。

$$
hash[i]=hash[i-1]*base+s[i]
$$

正确的哈希递推式子长这样，相当于我们把第一位看成最高位，和我们的数字写法一样。

## AC代码

[https://atcoder.jp/contests/abc398/submissions/64119843](https://atcoder.jp/contests/abc398/submissions/64119843)

```cpp
// Problem: F - ABCBA
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Spring (AtCoder Beginner Contest 398)
// URL: https://atcoder.jp/contests/abc398/tasks/abc398_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll base=131;

ll N,M,T,A[MAXN];
ull hashe[MAXN],hashrs[MAXN];
ull powBase[MAXN];


inline void solve(){
	string s;
	cin>>s;
	string rs(s.rbegin(),s.rend());
	rs='0'+rs;
	N=SZ(s);
	if(N==1){
		cout<<s<<"\n";
		return;
	}
	powBase[0]=1;
	FOR(i,1,N){
		powBase[i]=powBase[i-1]*base;
	}
	s='0'+s;
	FOR(i,1,N){
		hashe[i]=hashe[i-1]*base+s[i];
	}
	FOR(i,1,N){
		hashrs[i]=hashrs[i-1]*base+rs[i];
	}
	FOR(i,N/2+1,N){
		ull len,suf,pre;
		// 以i的前面作为对称中心
		len=N-i+1;
		suf=hashrs[len]-hashrs[0]*powBase[len];
		pre=hashe[i-1]-hashe[i-len-1]*powBase[len];
// #ifdef LOCAL
    // cerr<<len<<" " <<i<<" "<< suf<<" "<<pre << '\n';
// #endif
		if(suf==pre){	
			FOR(i,1,N){
				cout<<s[i];
			}
			FOR(i,len*2+1,N){
				cout<<rs[i];
			}
			cout<<"\n";
			return;
		}
		// 以i作为对称中心
		len=N-i;
		suf=hashrs[len]-hashrs[0]*powBase[len];
		pre=hashe[i-1]-hashe[i-len-1]*powBase[len];
		if(suf==pre){	
			FOR(i,1,N){
				cout<<s[i];
			}
			FOR(i,len*2+2,N){
				cout<<rs[i];
			}
			cout<<"\n";
			return;
		}

	}
	FOR(i,1,N){
		cout<<s[i];
	}
	FOR(i,1,N){
		cout<<rs[i];
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc398/submissions/64119843
*/
```

## 心路历程（WA，TLE，MLE……）