从十进制理解字符串哈希

字符串哈希，是将字符串转换成哈希值的一种做法，我更偏向于将其称作字符串转数值进制。

首先，我们看这样的一道题：

字符串哈希

给定一个长度为 $n$ 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l_1, r_1, l_2, r_2$ ，请你判断 $[l_1, r_1]$ 和 $[l_2, r_2]$ 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 $n$ 和 $m$ ，表示字符串长度和询问次数。

第二行包含一个长度为 $n$ 的字符串，字符串中只包含大小写英文字母和数字。

接下来 $m$ 行，每行包含四个整数 $l_1, r_1, l_2, r_2$ ，表示一次询问所涉及的两个区间。
注意，字符串的位置从 $1$ 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。

数据范围

$1 \le n, m \le 10^5$

输入样例：
8 3

aabbaabb

1 3 5 7

1 3 6 8

1 2 1 2

输出样例：
Yes
No
Yes


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int n=1;
        while(n-->0) solve();
        out.flush();
    }
    static int N= (int) (1e5+10),P=131;
    static long []base=new long[N],h=new long[N];
    static void solve(){
        int n=in.nextInt(),q=in.nextInt();
        String a=in.next();
        base[0]=1;
        for(int i=1;i<=n;i++){
            base[i]=base[i-1]*P;
            h[i]=h[i-1]*P+a.charAt(i-1);
        }
        for(int i=1;i<=q;i++){
            int l1,r1,l2,r2;
            l1=in.nextInt();r1=in.nextInt();l2=in.nextInt();r2=in.nextInt();
            if(getHash(l1,r1)==getHash(l2,r2)){
                out.println("Yes");
            }else{
                out.println("No");
            }
        }
    }
    static long getHash(int l,int r){
        return h[r]-h[l-1]*base[r-l+1];
    }
    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

其实这便是把字符串转换成了数值形式，不过这个数值是P进制。现在我们来用十进制模拟一下字符串哈希。
首先我们假设有一个十进制数123421，我们从左到右定义6个位置的哈希值分别是1、12、123、1234、12342、123421。
现在我们想求34的哈希值，过程如下：

用1234减去12,那么得到1222。
在上一步我们发现求出不对，所以我们要对12补0。
补的0的位数便是要求的34的长度，于是便是1234-1200=34。
体现在代码里便是

1
2
3

static long getHash(int l,int r){
    return h[r]-h[l-1]*base[r-l+1];//补P进制下的r-l+1位
}

Remove Two Letters

给定一个长度为 $n$ 的字符串，可以删除 $2$ 个连续字符，问有多少个不同的字符串

字符串中只包含小写英文字母。

输入格式

第一行包含整数 $t$ ，表示案例数量。

第二行包含整数 $n$ ，表示字符串长度。

第三行包含一个长度为 $n$ 的字符串，字符串中只包含小写英文字母。

输出格式

一个整数，表示删去 $2$ 个连续字符后，不同的字符串的数量。
每个结果占一行。

数据范围

$3 \le n \le 2·10^5$
对于所有的 $n$ 之和， $3 \le sum(n) \le 2·10^5$
输入样例：
7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa

输出样例：
4
1
5
3
3
3
1


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int n=in.nextInt();
        while(n-->0) solve();
        out.flush();
    }
    static int N= (int) (2e5+10),P=13331;
    static long[]h=new long[N],p=new long[N];
    static void solve(){
        int n=in.nextInt();
        String s=in.next();
        p[0]=1;
        for(int i=1;i<=n;i++){
            p[i]=((p[i-1]*P));
            h[i]=((h[i-1]*P+s.charAt(i-1)-'a'));
        }
        Set<Long> set=new HashSet<>();
        for(int i=2;i<=n;i++){
            long k=get(1,i-2)*p[n-i]+get(i+1,n);
            set.add(k);
        }
        out.println(set.size());
    }
    static long get(int l,int r){
        if(l>r)  return 0;
        return (h[r]-h[l-1]*p[r-l+1]);
    }
    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

现在，我们想求删除连续若干个字符得到的哈希值，假设我们要求1221，从123421中挖去34。

我们利用上述的方法得到12，21。
我们将12，也就是被挖去字符的上一个位置（设其为pos）补0。
补0的数量是pos位置后不为空的字符数。这里是2
12补2个0，为1200，1200+21=1211

体现在代码中便是:

1	long k=get(1,i-2)*p[n-i]+get(i+1,n);//n-i为后缀字符数量