标签：hash int long times 字符串 Hash 初等

$CuO + CO \triangleq Cu + CO_2 $

初等字符串

字符串Hash

---

\(\bf{Hash}:\)一种好用又cd的算法

\(·First\)

如果要比较两个字符串的大小，开\(string\)两两比较是\(O(n)\)の算法如果进行\(m\)次比较的话$O( m \times n ) $显然去世

考虑\(O(m)\)の算法 , 即让比较过程变为\(O(1)\)

那么如果可以将字符串表示成一个数，那么就好说很多了。

如何用k进制来表示一个数?

\(eg:\)

\[(114514)_{10} \ = \ \ \ \ ( \ ? \ )_k \]

......

其实字符串也可以这么表示,最后の值叫他 Hash 值

对于字符串\(s_1s_2s_3.....s_n\)

我们可以用\(hash_s\)表示

那么\(hash_s:\)
$$ hash_s ={!!!!!!}= s_1*k^{n-1} \times s_2 \times k ^{n-2} \times s_3 \times k^{n-3} \times ... \times s_n \times k^0 $$
其中\(k\)是一个\(\ge\)字符串中最大字符大小の数\((例：Cekasauk中の's')\)，最好是个素数(前置知识·素数)

我用\(131\)较习惯

此时是不是觉得\(hash\)非常好用?

\(\mathrm{·美中不足:\color{red}哈希冲突}\)

\(\because\)对于字符来说,\(0\)的值是\(48\)

\(\therefore\)任一其他字符都会很大

如果我在每一个字符上都乘上一个\(131^\alpha\)次方，再乘起来 ， 很有可能爆 $long \ long $

\(\therefore\)在计算字符串哈希值时，再摸一个大整数(最好是素数)

这时就可以知道一个字符串の\(hash\)值了。

\(\color{blue}But:\)

$ mod \ p $ 带来の问题十分明显了。

如果两个字符串不相等，但\(mod\)让他们整好相等了，\(hash\)值返回的就是\(WA\)的。

这就叫做哈希冲突。

哈希冲突无法避免，但可以考虑优化。

$·考虑优化\implies second ： \ hash \ の优化 $

1. 双模数哈希

   模一个数\(p\)如果不准的话就再模一个数\(q\),且\(gcd( \ p \ , \ q \ ) \ ={\!\!\!\!\!\!}= 1\)

   精准很多

2. $ unsigned \ long \ long $

   如果模数太小导致哈希冲突の话，就想方法让模数尽可能的大。

   $ unsigned \ long \ long $ : 是很不错的选择。

   \(2^{64}-1の超大存储量\) ,oppo23,模出你的美

   $ but $ 永远不是完美的

   $unsigned \ long \ long \(是一个\)\rm{很好卡的数值}$。

   出题人会卡死你。
   但平常の题用它还是很不错的。

---

\(code:(\ of \ unsigned \ long \ long \ )\)

#define int unsigned long long 
using namespace std ; 
const int down = 131 //底数
int does[ N ] ; // down^k
string s ; // 模式串
string b[ N ] ; 
int n ; 
int hash_s , hasher[ N ] ; 
inline void Make_Hash( string s , int &hashwer )
{
    int len = s.size( ) ; 
    for ( int i = 0 ; i < len ; ++ i )
    {
        hashwer += s[ i ] * does[ n - i + 1 ] ; // 看做从一开始
    }
}
signed main( )
{
    cin >> n ; 
    cin >> s ; 
    Make_Hash( s , hash_s ) ; 
    for( int i = 1 ; i <= n ; ++ i )
    {
        cin >> b[ i ] ; 
        Make_Hash( b[ i ] , hasher[ i ] ) ; 
        if( hasher[ i ] == hash_s )
        cout << "Yes" << '\n' ;
        else cout << "Fucking Bich " << '\n' ; 
    }
}

\(·Third - hash \ 求前缀和\)

如果只能比较单个字符串，这个算法就太\(\color{white}逊\)了。

\(\therefore\) 这里有这么个题:

给定模式串b , 目标串s , 求在目标串中的前缀[1,r]是否等于b

\(s\)中前\(i\)个元素

\[\ \ \ \ hash_i = s_1 \times k ^ { n - 1 } \times s_2 \times k ^ { n - 2 } \times ... \times s_i \times k ^{ n - i } \]

\[hash_b = b_1 \times k ^ { i - 1 } \times b_2 \times k ^ { i - 2 } \times ... \times b_i \times k^0 \]

你要让\(b = \!\!= s[ \ 1 \ , \ r \ ]\)

那么b.size( )一定 \(=\!\!=\) s[ 1 , r ].size( )

让\(hash_b\)左右同时乘$k^{ n - i } $

\[hash_b \times k ^{ \ n \ - \ i \ } =\!\!= b_1 \times k ^ { n - 1 } \times b_2 \times k ^ { n - 2 } \times b_i \times k ^ { n - i } \]

\(\because\)模过了数 $ \ \ \ $ \(\therefore\) 不能再除了\((不要和我一样sb)\)

\(\therefore\)只需要比较 \(hash_i\) $ and $ $ hash_b \times k ^{ n - i } $

$ ·Fourth $

求在目标串中与模式串相等の个数

运用\(Thrid\)の知识，自己想(md烦不想写)

标签：hash,int,long,times,字符串,Hash,初等
From： https://www.cnblogs.com/hangry/p/18000480