本文共 3089 字，大约阅读时间需要 10 分钟。
题目：
很久很久以前，森林里住着一群兔子。
有一天，兔子们想要研究自己的 DNA 序列。
我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。
然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。
注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。
输入格式
第一行输入一个 DNA 字符串 S。第二行一个数字 m，表示 m 次询问。
接下来 m 行，每行四个数字 l1,r1,l2,r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。
输出格式
对于每次询问，输出一行表示结果。如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）。
数据范围
1≤length(S),m≤1000000 输入样例： aabbaabb 3 1 3 5 7 1 3 6 8 1 2 1 2 输出样例： Yes No Yes题意：
m 个 询 问 ， 每 次 给 定 两 个 区 间 ， 判 断 两 个 区 间 的 子 串 是 否 相 等 。 m个询问，每次给定两个区间，判断两个区间的子串是否相等。 m个询问，每次给定两个区间，判断两个区间的子串是否相等。
字符串哈希算法
将 给 定 字 符 串 视 作 一 个 P 进 制 的 数 ， 再 对 其 每 一 个 前 缀 进 行 求 值 并 映 射 到 h a s h 数 组 中 ， 当 需 要 对 该 字 符 串 中 的 子 串 进 行 比 较 时 , 就 可 以 用 O ( 1 ) 的 时 间 快 速 查 询 某 段 子 串 的 哈 希 值 。 为 了 避 免 冲 突 ， P 通 常 取 一 些 质 数 。 将给定字符串视作一个P进制的数，再对其每一个前缀进行求值并映射到hash数组中，当需要对该字符串中的子串\\进行比较时,就可以用O(1)的时间快速查询某段子串的哈希值。为了避免冲突，P通常取一些质数。 将给定字符串视作一个P进制的数，再对其每一个前缀进行求值并映射到hash数组中，当需要对该字符串中的子串进行比较时,就可以用O(1)的时间快速查询某段子串的哈希值。为了避免冲突，P通常取一些质数。
EG:
举 例 ： 字 符 串 s t r = " a b c a b " ， 取 P = 131 ， 即 将 s t r 看 作 是 一 个 131 进 制 的 数 ， a b c d . . . 视 作 1 , 2 , 3 , 4... 。 举例：字符串str="abcab"，取P=131，即将str看作是一个131进制的数，abcd...视作1,2,3,4...。 举例：字符串str="abcab"，取P=131，即将str看作是一个131进制的数，abcd...视作1,2,3,4...。① 、 对 其 每 一 个 前 缀 求 值 , 用 数 组 h 来 存 储 ： ①、对其每一个前缀求值,用数组h来存储： ①、对其每一个前缀求值,用数组h来存储：
h [ 1 ] = a = 13 1 0 × 1 ， h [ 2 ] = a b = 13 1 1 × 1 + 13 1 0 × 2 ， h [ 3 ] = a b c = 13 1 2 × 1 + 13 1 1 × 2 + 13 1 0 × 3 , h [ 4 ] = a b c a = 13 1 3 × 1 + 13 1 2 × 2 + 13 1 1 × 3 + 13 1 0 × 1 , h [ 5 ] = a b c a b = 13 1 4 × 1 + 13 1 3 × 2 + 13 1 2 × 3 + 13 1 1 × 1 + 13 1 0 × 2 。 h[1]=a=131^0×1，\\h[2]=ab=131^1×1+131^0×2，\\h[3]=abc=131^2×1+131^1×2+131^0×3,\\h[4]=abca=131^3×1+131^2×2+131^1×3+131^0×1,\\h[5]=abcab=131^4×1+131^3×2+131^2×3+131^1×1+131^0×2。 h[1]=a=1310×1，h[2]=ab=1311×1+1310×2，h[3]=abc=1312×1+1311×2+1310×3,h[4]=abca=1313×1+1312×2+1311×3+1310×1,h[5]=abcab=1314×1+1313×2+1312×3+1311×1+1310×2。② 、 计 算 子 串 的 哈 希 值 ： ②、计算子串的哈希值： ②、计算子串的哈希值：
可 见 ， h [ i ] = h [ i − 1 ] × 131 + ( s t r [ i ] − ′ a ′ + 1 ) 。 计 算 区 间 [ l , r ] 之 间 字 符 串 对 应 哈 希 值 = h [ r ] − h [ l − 1 ] × 13 1 r − l + 1 。 注 意 ： 因 为 下 标 小 的 字 符 在 高 位 ， 我 们 在 作 差 过 程 中 要 将 前 缀 先 乘 上 数 量 级 的 差 。 因 此 我 们 用 p 数 组 存 储 13 1 i 。 可见，h[i]=h[i-1]×131+(str[i]-'a\ '+1)。计算区间[l,r]之间字符串对应哈希值=h[r]-h[l-1]×131^{r-l+1}。\\注意：因为下标小的字符在高位，我们在作差过程中要将前缀先乘上数量级的差。因此我们用p数组存储131^i。 可见，h[i]=h[i−1]×131+(str[i]−′a ′+1)。计算区间[l,r]之间字符串对应哈希值=h[r]−h[l−1]×131r−l+1。注意：因为下标小的字符在高位，我们在作差过程中要将前缀先乘上数量级的差。因此我们用p数组存储131i。模板代码:
#include#include #include #define ull unsigned long longusing namespace std;const int N=1e6+10;const int base=131;int n ,m;ull h[N],p[N];ull get(int l,int r){ return h[r]-h[l-1]*p[r-l+1];}char s[N];int main(){ scanf("%s",s+1); n=strlen(s+1); ///strlen(字符串首地址) cin >> m; p[0]=1; for(int i=1;i<=n;i++) { h[i]=h[i-1]*base+s[i]-'a'+1; p[i]=p[i-1]*base; } int l1,r1,l2,r2; while(m--) { scanf("%d%d%d%d",&l1,&r1,&l2,&r2); if(get(l1,r1)==get(l2,r2)) printf("Yes\n"); else printf("No\n"); } return 0;}
转载地址：http://vcor.baihongyu.com/