算法基础之字符串哈希

字符串哈希

• 核心思想：用p(131或者13331)进制数储存字符串每一位数的hash值

  • 

  • L—R的哈希值 = h[R]-h[L-1]*P^R-L+1

  • 哈希值很大—>modQ(2⁶⁴)变小 == 用unsigned long long 存 (出界)

  •   #include
      using namespace std;
      typedef unsigned long long ULL;
      const int N=100010,P=131;  //P用131 Q用2的64次方 冲突可忽略
      
      int n,m;
      char str[N];
      ULL h[N],p[N];
      
      ULL get(int l,int r){ 
          return h[r] - h[l - 1]*p[r-l+1];  //推导的公式 求出l到r区间的哈希值
      }
      int main(){
          scanf("%d%d%s" , &n,&m,str+1);
          
          p[0]=1;
          for(int i=1;i<=n;i++){
              p[i] = p[i-1] *P;  //保存p的多少次方
              h[i] = h[i-1] *P+str[i];  //越往右越大
          }
          while(m--){
              int l1,r1,l2,r2;
              cin>>l1>>r1>>l2>>r2;
              
              //如果哈希值相等 即字符串相同
              if(get(l1,r1) == get(l2,r2)) printf("Yes\n");
              else printf("No\n");
          }
      }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29

• 解惑：

  • **1.**h[i]为什么越来越大？不应该从左到右减小吗？

    答：因为h[L]n才能跟h[R]在同一个位次相减