hdu 4622 Reincarnation 字符串hash 模板题

时间：2021-02-04 05:16:01

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4622

题意：给定一个长度不超过2000的字符串，之后有不超过1e5次的区间查询，输出每次查询区间中不同的子串个数？

做法1：字符串hash

一般的做法就是模拟每段子串的长度L（从1到 len）,这样时间复杂度为O(n^2);但是里面并没有计算子串比较是否相等以及存储的时间，而这段时间就是将字符串看成是“数字”，这样存储和比较的时间均降为O(1)了；

下面讲讲模板；

1.如何将字符串看成一个“高精度的数字”，由于相同的子串不只是含有的字符个数的和字符类别要相同，同时还需要和数字一样分成在“什么位”上（如十位还是百位）；下面的p[]就是这样一个表示在哪一位；同时s[i]表示的就是子串str[0...i-1]，只不过表示成了数字的形式；这样之后就可以直接枚举长度L,并且将是否有重复的给“标记”下来；

注意:ans[pos][i+L-1] :表示的是只有子串起点在pos（其实之后的二维DP求和可以扩大到更大的区间），终点在i+L-1才需要-1；不是pos+L-1

2.将上面的标记累加起来，递推出二维的ans[][];即区间长度从小到大递推即可；

时间空间复杂度均为O(n^2)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define HASH 10007

 #define MAXN 2007

 struct StringMap{

     int head[HASH],Next[MAXN],tot;

     unsigned long long state[MAXN];

     int f[MAXN];

     void init(){

         tot = ;

         memset(head,-,sizeof(head));

     }

     int ins(unsigned long long val,int id)

     {

         int h = val%HASH;

         for(int i = head[h];i != -;i = Next[i]){

             if(val == state[i]){

                 int tmp = f[i];

                 f[i] = id;

                 return tmp;

             }

         }

         f[tot] = id;

         state[tot] = val;

         Next[tot] = head[h];

         head[h] = tot++;

         return ;

     }

 }H;

 char str[MAXN];

 const int SEED = ;

 unsigned long long p[MAXN];

 unsigned long long s[MAXN];

 int ans[MAXN][MAXN];

 int main()

 {

     //freopen("in.txt","r",stdin);

     p[] = ;

     for(int i = ;i < MAXN;i++)

         p[i] = p[i-]*SEED;

     int T;

     scanf("%d",&T);

     while(T--){

         scanf("%s",str);

         int len = strlen(str);

         s[] = ;

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

             s[i] = s[i-]*SEED+str[i-];

         memset(ans,,sizeof(ans));

         for(int L = ;L <= len;L++){

             H.init();

             for(int i = ;i+L- <= len;i++){

                 int pos = H.ins(s[i+L-]-s[i-]*p[L],i);

                 ans[i][i+L-]++;

                 ans[pos][i+L-]--;        //做标记

             }

         }

         for(int i = len;i >= ;i--)

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

                 ans[i][j] += ans[i+][j] + ans[i][j-] - ans[i+][j-];  //递推出所有结果

         int Q,l,r;

         scanf("%d",&Q);

         while(Q--){

             scanf("%d%d",&l,&r);

             printf("%d\n",ans[l][r]);

         }

     }

 }

相关文章