哈希Hash在字符串中的应用

　　本文含有原创题，涉及版权利益问题，严禁转载，违者追究法律责任

　　哈希大家都会用撒，字符串显然都会写撒，那么哈希离散化字符串不就懂了？！（XXX的神逻辑，其实原文是：树都晓得吧，数组显然都会开呀，那么恭喜你学会了树状数组！）

　　例如我们给出 n 个长度为 m 的字符串，然后给你一个长度为 m 的字符串 s ，求 s 是否在之前的 n 个串中出现过

　　暴力扫 n 个串，然后一位位去对，看是否相等，时间复杂度O(nm)，它非常得辣鸡

　　当然我们可以建一颗 trie 树做，但是建树的复杂度也是O(nm)的，对于只询问一次还不如打暴力

　　一阵思考后，我们选用非常优秀的哈希（以下简称Hash）

　　（机制的人请忽略这篇文章）

　　平常我们用 Hash 是对数字进行处理，一般把它取模之后离散化到各个数组

　　但是对于字符串呢？难道把它所有位加起来取模？显然是不行的，如 ab 和 ba 这两种情况是相同的，那么小节点挂的链会很多

　　于是乎，我们想，对于字符串只有256种，而题目中给的一般只会包含字母，甚至是只有小写字母，瞬间压缩到26种

　　那么我们可以把它前面 k 位取出来，如取4位出来是 axoc，把它装换成对应的数字是 0 23 14 2 （a 看做 0，b 看做 1 …… z 看做 25）

　　这不就是一个二十六进制数！

　　把前 k 位取出来，第 i 位即为这个26进制数的第 i 位，再把它转换为10进制，如 axoc 为 45214，这样我们就得到了 Hash 的 Hash 函数了

　　字符串判重就容易了， Hash 具体实现过程就不用讲了吧

　　对于 26 进制的数，int 范围下只能取到第 6 位，long long范围下可以取到第 13 位

　　下面给道例题

　　题意很简单，给你一个串，求他有多少个不同的子串，满足前缀为A，后缀为B。需要注意的是，串中所有的字母都是小写字母。

　　三个串长度均小于等于 2000，时间1s，空间128MB

　　样例输入：abababab

　　样例输出：4

　　直接暴力枚举然后 Hash 判重，我们这里截取前3位做 Hash 函数

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N=,loc=,power[]={,,,,,,,},mo=;

 struct Hash

 {

     int next;

     char s[N];

 }

     hs[N*];

 char a[N],b[N],s[N];

 int ls,ans,next[N],f[N],top,first[mo],tg,g[mo];

 bool fa[N],fb[N];

 void init(char c[N],int len)

 {

     int i,j=;

     for (i=;i<len;i++)

     {

         while (j&&c[i]!=c[j]) j=next[j];

         if (c[i]==c[j]) j++;

         next[i+]=j;

     }

 }

 void kmp(char c[N],int len)

 {

     int i,j=;

     top=;

     for (i=;i<=len;i++) next[i]=;

     init(c,len);

     for (i=;i<ls;i++)

     {

         while (j&&s[i]!=c[j]) j=next[j];

         if (s[i]==c[j]) j++;

         if (j==len)

         {

             f[++top]=i-j+;

             j=next[j];

         }

     }

 }

 void hash(char c[N],int len)

 {

     int i,x=,t=min(len,loc);

     for (i=;i<=t;i++) x+=(c[i]-'a')*power[i];

     if (first[x]) for (i=first[x];i;i=hs[i].next)

     {

         t=len-loc;

         if (t<=) return;

         for (x=;x<=t;x++) if (hs[i].s[x]!=c[loc+x]) break;

         if (x>t) return;

     }

     if (!(hs[++top].next=first[x])) g[++tg]=x;

     first[x]=top;

     x=;

     for (i=loc+;i<=len;i++) hs[top].s[++x]=c[i];

     ans++;

 }

 int main()

 {

     int la,lb,i,j,t,x,k,l;

     char c[N];

     scanf("%s\n%s\n%s\n",&s,&a,&b);

     ls=strlen(s);

     la=strlen(a);

     lb=strlen(b);

     kmp(a,la);

     for (i=;i<=top;i++) fa[f[i]]=;

     kmp(b,lb);

     for (i=;i<=top;i++) fb[f[i]]=;

     t=ls-la-lb;

     for (j=;j<=t;j++)

     {

         for (i=;i<=tg;i++) first[g[i]]=;

         top=tg=;

         for (i=;i<=t-j;i++)

         {

             x=i+j+la;

             if (fa[i]&&fb[x])

             {

                 l=;

                 for (k=i+la;k<x;k++) c[++l]=s[k];

                 hash(c,j);

             }

         }

     }

     for (i=max(la-lb-,);i<=la;i++)

     {

         j=i;

         while (a[j]==b[j-i]) j++;

         if (a[j]!='\0') continue;

         for (j=;j<i;j++) c[j]=a[j];

         for (k=;k<lb;k++,j++) c[j]=b[k];

         kmp(c,j);

         if (top) ans++;

     }

     printf("%d\n",ans);

     return ;

 }

　　据说可以用KMP或者EXKMP做orz

　　还有我的程序在 Hash 取别的位数的时候会 WA 几个点（而且还是不同的点？？）

　　求助大神能解释一下orz（再次体现我的蒟蒻）

　　注：该题为原创题，可购买数据，价格 RMB 2.0

　　如需购买在这 Get 联系方式 http://www.cnblogs.com/hadilo/p/5932395.html

巴特西

哈希Hash在字符串中的应用_C++

最新文章

热门文章