题目 字符串哈希

https://oi-wiki.org/string/hash/

字符串哈希求数组

表示为

\[hash[i] = (hash[i - 1] * b + ss[i]) \% mod\]

字符串哈希求解子串哈希值

\[ h[r] - (h[l - 1] * bs[r - l + 1]) \% mod + mod) \% mod \]

题目1460. 我在哪？

https://www.acwing.com/problem/content/1462/

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f

const ll mod=998244353;
const ll b=133;

char ss[110];
ll h[110];
ll bs[1010];

int main(){
	int n;
	cin>>n;
	cin>>ss;
	bs[0]=1;
	for(int i=1;i<=110;i++){
		bs[i]=bs[i-1]*b;
		bs[i]%=mod;
		// printf("%lld ",bs[i]);
	}
	h[0]=ss[0]-'A'+1;
	for(int i=1;i<n;i++){
		h[i]=h[i-1]*b+ss[i]-'A'+1;
		h[i]%=mod;
		// printf("%lld\n",h[i]);
	}
	// printf("ENS::%d\n",(h[6]-(h[3]*bs[3])%mod+mod)%mod);
	int lside=1,rside=n;
	while(lside!=rside){
		int mid=(lside+rside)>>1;
		unordered_map<int,int> hash;
		bool flag=false;
		for(int l=0,r=l+mid-1; r!=n ; l++,r++){
			ll key=0;
			if(l==0){
				key=h[r];
			}
			else{
				key=(h[r]-h[l-1]*bs[mid]%mod+mod)%mod;
				// cout<<"KEY:::"<<key<<endl;
			}
			if(hash[key]){
				//test:::
				// cout<<"KEY::"<<key<<endl; 
				flag=true;
				break;
			}
			else{
				hash[key]=1;
			}
		}
		if(flag){
			lside=mid+1;
		}
		else{
			rside=mid ;
		}
	}
	cout<<lside<<endl;
	return 0;
}