#C241102B. 串串串

标签（Label）

• 哈希
• 思维

网址（Website）

题目详情 - 串串串 - Super

题解 - 串串串 - Super

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 101234;
const int bas = 131ll;
bool ST;

int fac[N],hsh[26][N];
string s;int n;

int rk[N][26], ord[N][26];
inline int calc(int l,int r,int c){return (hsh[c][r]-hsh[c][l-1]*fac[r-l+1]%mod+mod)%mod;}

void Solve(){
	cin>>s;n=s.size();s=" "+s;
	For(i,0,25) ord[n+1][i]=rk[n+1][i]=i;
	Rof(i,n,1){
		memcpy(ord[i], ord[i+1], sizeof ord[0]);
		memcpy(rk[i], rk[i+1], sizeof rk[0]);
		int p = rk[i][s[i]-'a']; rk[i][s[i]-'a']=0;
		For(j,0,p-1) rk[i][ord[i][j]]++;//下面的排名移上去 
		Rof(j,p,1) ord[i][j] = ord[i][j-1];//转移排名 
		ord[i][0] = s[i] - 'a';
	}
	
	fac[0]=1;For(i,1,n) fac[i]=fac[i-1]*bas%mod;
	For(c,0,25) For(i,1,n)
		hsh[c][i] = (hsh[c][i-1]*bas+(s[i]-'a'==c))%mod;
	
	int ans = n;
	Rof(i,n-1,1){
		int l=0,r=n-ans+2;while(l<r){
			int mid = (l+r+1)>>1;bool tag=true;
			for (int j = 0; j < 26; j++) {
				int h1 = calc(i,i+mid-1, ord[i][j]);
				int h2 = calc(ans, ans+mid-1, ord[ans][j]);
				tag &= h1 == h2;
			}if(tag) l=mid;else r=mid-1;
		}
		if(l == n-ans+1) ans=i;
		else if(rk[i][s[i+l]-'a'] < rk[ans][s[ans+l]-'a']) ans = i;
	}For(i,ans,n) cout<<char('z'-rk[ans][s[i]-'a']);cout<<'\n'; 
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("str.in","r",stdin);
	freopen("str.out","w",stdout);
	int T=rd();double Tim=clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}