字符串前缀哈希法:
h[0]=0,h[1]=’A’,h[2]=’AB’,h[3]=’ABC’ 左边高位右边低位!!
p0 p1p0 p2p1p0
l到r位字符:h[r]-h[l-1]*p^(r-l+1)
把字符串的每一位看成p进制数;(P=131或13331,Q=2^64)
由于数字太大要%Q,映射0-Q-1
java 代码
import java.util.*;
public class Main{
static int n,m;
static int N=100010,P=131;
static long[] h=new long[N];
static long[] p=new long[N];
public static long get(int l,int r){
return h[r]-p[r-l+1]*h[l-1];
}
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
char[] s=scan.next().toCharArray();
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=P*h[i-1]+s[i-1];//前缀和
p[i]=p[i-1]*P;
}
while(m-->0){
int l1=scan.nextInt();
int r1=scan.nextInt();
int l2=scan.nextInt();
int r2=scan.nextInt();
if(get(l1,r1)==get(l2,r2))System.out.println("Yes");
else System.out.println("No");
}
}
}
%%%