进制哈希公式推导

1、哈希：

           哈希就像是给一串明文加密，加密后的数字尽可能不出现密文相同的情况，就像是同一把钥匙不能轻易打开两个锁。

           哈希能解决的问题很典型，类似判断一个串在另一个串中出现过几次：题解链接

2、进制哈希：

           加密方式有很多种，这里讲解的主要是进制哈希，即把一串明文转换成k进制的数字。

           k的选取很重要，k取不同值时密文可能会出现相同数字,可能会wa。

例如：

给出字符串ABABAB（明文），将他转换成数字密文。

公式：ha[i]=ha[i+1]*k+a[i] (a中存明文，ha[] 为int型)

代码：

（代码中没有取余，la很大的时候肯定会爆int，下面有具体说明）

void hasha(string a)
{
    LL la=a.size();
    la-=1;
    for(LL i=la;i>=1;i--){
        ha[i]=ha[i+1]*k+a[i];
    }
}

爆int的问题：

如果是单纯比较两个数的hash值，不会影响最终结果（因为即使成了负数只要两个数相同就行）。

但如果要先保存一个hash值再与后面的比较，最好先取余并用LL存hash值。

3、进制hash推导公式：

    a.求连续字符串的hash值：

    推导过程：

    代码：

1366=ha[1]-ha[5]*pow(k,x)；

b.求不连续字符串的hash值：题目链接 或 题解

做题时遇到了个难题，就是求出了663141123的hash值，但还要计算出6634的hash值，即：在一个片段中去掉一些字符，求剩余的 hash值，不知道怎么弄，有个简单的方法就是令k=10，用10进制能很快推出公式。

推导过程：

代码：

4366=(ha[4]-ha[5]*pow(k,y))*qpow(k,x)+ha[1]-ha[4]*pow(k,x)；