【ACWing】138. 兔子与兔子

题目地址：

https://www.acwing.com/problem/content/140/

很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含26 2626个小写英文字母）。然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式：
第一行输入一个DNA字符串S SS。
第二行一个数字m mm，表示m mm次询问。
接下来m mm行，每行四个数字l 1 , r 1 , l 2 , r 2 l_1,r_1,l_2,r_2l1​,r1​,l2​,r2​，分别表示此次询问的两个区间，注意字符串的位置从1 11开始编号。

输出格式
对于每次询问，输出一行表示结果。
如果两只兔子完全相同输出Yes，否则输出No（注意大小写）。

数据范围：
1 ≤ l e n g t h ( S ) , m ≤ 1000000 1≤length(S),m≤10000001≤length(S),m≤1000000

字符串哈希。代码如下：

#include<iostream>#include<cstring>usingnamespacestd;usingull=unsignedlonglong;constintN=1e6+10,P=131;intn,m;chars[N];ull ha[N],po[N];ullget_hash(intl,intr){returnha[r]-ha[l-1]*po[r-l+1];}intmain(){scanf("%s",s+1);scanf("%d",&m);n=strlen(s+1);po[0]=1;for(inti=1;i<=n;i++){ha[i]=ha[i-1]*P+s[i];po[i]=po[i-1]*P;}while(m--){intl1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);puts(get_hash(l1,r1)==get_hash(l2,r2)?"Yes":"No");}}

预处理时间复杂度O ( l S ) O(l_S)O(lS​)，每次询问时间O ( 1 ) O(1)O(1)，空间O ( l S ) O(l_S)O(lS​)。