HASH求两子串是否相等(O(N)预处理O(1)比较)

xiaoxiao2021-02-28  105

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> using namespace std; const int MAXN = 5010; const unsigned long long SEED = 13331; unsigned long long P[MAXN]; unsigned long long S[MAXN]; unsigned long long RS[MAXN]; string s; int n; unsigned long long HS( int l, int r ){//正向 if( l == r ){ return s[l]; } l++; r++; return S[r] - S[l-1] * P[r-l+1]; } unsigned long long RHS( int l, int r ){//反向 if( l == r ){ return s[l]; } l = n - l - 1; r = n - r - 1; swap( l, r ); l++; r++; return RS[r] - RS[l-1] * P[r-l+1]; } int main(){ cin >> s; P[0] = 1; for( int i = 1; i < MAXN; i++ ){ P[i] = P[i-1] * SEED; } n = s.size(); for( int i = 1; i <= n; i++ ){ S[i] = S[i-1] * SEED + s[i-1]; } for( int i = 1; i <= n; i++ ){ RS[i] = RS[i-1] * SEED + s[n-i]; } cout << (HS(0,3 ) == HS( 6,9 )) << endl; return 0; }
转载请注明原文地址: https://www.6miu.com/read-57640.html

最新回复(0)