公式證明
在之前的某一篇部落格中我寫了，關于BDKRHash的簡短的介紹，還沒有對其公式和原理進行闡述，實在是罪過罪過。
首先給出BDKRHash的公式
1.$$hashvalue[i]=(hashvalue[i-1]*seed+str[i]-'a'+1)%P$$（也可以用ASCLL碼值，但容易爆)
2.$$Hashvalue[l……r]=(hashvalue[r]-hashvlaue[l-1]*seed^{r-l+1})%P$$（注意第一個Hashvalue與hashvalue不同）
第一個公式不需要證明，這是BDKRHash的定義式，意思就是：發明BDKRHash的人就是這麼寫的。這個東西隻有用記憶的方法來掌握，如果要深究其原理，太過深奧，蒟蒻我不懂。
接下來我們針對第二個公式進行證明： Hashvalue代表的是從l到r這個區間的字串的hash值，hashvalue代表從第1個開始到第i個的hash值。下面開始證明
先看第一個公式
$$hashvalue[i]=(hashvalue[i-1]*seed+str[i]-'a'+1)%P$$
我們把每一項展開可以得到（為友善表達，接下來hashvalue簡寫為hash，str[i]-'a'+1簡寫為str[i]）
$$hash[0]=0$$
$$hash[1]=str[1]%P$$
$$hash[2]=hash[1]*seed+str[2]$$
$$hash[3]=hash[2]*seed+str[3]$$
$$hash[i]=hash[i-1]*seed+str[i]$$
$$hash[n]=hash[n-1]*seed+str[n]$$
看出一些規律了嗎？如果沒有，我們再把每一項中的hash[i]*seed展開：
$$hash[2]=(str[1])*seed+str[2]$$
$$hash[3]=(str[1]*seed+str[2])*seed+str[3]$$
$$hash[4]=((str[1]*seed+str[2])*seed+str[3])*seed+str[4]$$
$$hash[i]=(((str[1]*seed+str[2])*seed+str[3])*seed······)*seed+str[i-1])+str[i]$$
再把括号全部展開：
$$hash[i]=str[1]*seed^{i-1}+str[2]*seed^{i-2}+······+str[i]*seed^{i-i=0}$$
到這裡我們已經大緻得到了BDKRHash的最終表達式，通過對這個式子進行變形，就可以得到第二個公式：
$$令l=1,則r=r-l+1$$
$$hash[l······r]=hash[1······r-l+1]=str[1]*seed^{r-l}+str[2]*seed^{r-l-1}+······+str[r-l+1]*seed$$
把1還原為l
$$hash[l······r]=str[l]*seed^{r-l}+str[l+1]*seed^{r-l-1}+······+str[r]*seed$$
寫到這裡，可能大家都已經明白了。
$$hash[1······l-1]=str[1]*seed^{l-2}+str[2]*seed^{l-3}+······+str[l-1]*seed\dashrightarrow①$$
$$hash[1······r]=str[1]*seed^{r-1}+str[2]*seed^{r-2}+······+str[r]*seed\dashrightarrow②$$
$$②-①*seed^{r-l+1}$$
得到 $$hash[1······r]=hash[1······l-1]*seed^{r-l+1}+str[l]*seed^{r-l}+str[l+1]*seed^{r-l-1}+······+str[r]*seed$$
$$hash[l······r]=str[l]*seed^{r-l}+str[l+1]*seed^{r-l-1}+······+str[r]*seed得$$
$$hash[l······r]=hash[1······r]-hash[1······l-1]*seed^{r-l+1}$$
又Hashvalue代表的是從l到r這個區間的字串的hash值，hashvalue代表從第1個開始到第i個的hash值。
$$Hashvalue[l……r]=(hashvalue[r]-hashvlaue[l-1]*seed^{r-l+1})%P$$
完結。 如果不懂，可以自己按着推一遍。
BDKRHash判斷回文字元串：
主要是通過下面這個式子判斷。
$$hash[i]=str[1]*seed^{i-1}+str[2]*seed^{i-2}+······+str[i]*seed$$
觀察之後不難發現，hash值是可以逆向來求的，即：
int seed=1;
for(int i=n;i>=1;i--)
{
hash[i]=hash[i+1]+str[i]*seed;
seed*=107;
} 是以我們隻用循環一遍就可以得到，1到i長度的字元串是不是回文字元串。
轉載于:https://www.cnblogs.com/Y-sofun/p/7576610.html