模板

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

兔子与兔子

题目描述

很久很久以前，森林里住着一群兔子。
有一天，兔子们想要研究自己的 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

题解

模板题，套用上面的模板即可

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef unsigned long long ULL;
const int N = 1000010, base = 131;
int h[N], p[N];
char str[N];

int get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * base + str[i] - 'a' + 1;
        p[i] = p[i - 1] * base;
    }
    
    int m;
    scanf("%d", &m);
    while(m--)
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d" , &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

回文子串的最大长度

题目描述

如果一个字符串正着读和倒着读是一样的，则称它是回文的。
给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。
输入格式
输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。
输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。
输出格式
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。
每个输出占一行。
输入样例：
abcbabcbabcba
abacacbaaaab
END
输出样例：
Case 1: 13
Case 2: 6

题解

套用字符串哈希算法。算出正序，逆序哈希。
枚举中点，然后二分半径。
技巧：在字符之间插入一个#，这样字符串长度就变成了偶数，但要注意的是：算原来字符长度的时候
要判断第一个字符是什么，如果不是#，这样字符长度就是半径+1，否则就是半径。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;
const int N = 2000010, base = 131;
char str[N];
ULL hl[N], hr[N], p[N];

ULL get(ULL h[], int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    
    int T = 1;
    
    while(scanf("%s", str + 1), strcmp(str + 1, "END"))
    {
        int n = strlen(str + 1);
        
        for(int i = 2 * n; i ; i -= 2) //在字符之间插入一个其他字符
        {
            str[i] = str[i / 2];
            str[i - 1] = 'a' + 26;
        }
        
        n = n * 2; //注意要更新n
        
        p[0] = 1;
        
        for(int i = 1, j = n; i <= n; i++, j--)
        {
            hl[i] = hl[i - 1] * base + str[i] -'a' + 1;
            hr[i] = hr[i - 1] * base + str[j] -'a' + 1;
            p[i] = p[i - 1] * base;
        }
        
        int res = 0;
        
        for(int i = 1; i <= n; i++) //枚举中点
        {
            int l = 0, r = min(i - 1, n - i);
            while(l < r) //二分半径
            {
                int mid = l + r + 1 >> 1;
                //算hr[]的时候要注意下标对应
                if(get(hl, i - mid, i - 1) != get(hr, n - (i + mid) + 1, n - (i + 1) + 1)) r = mid - 1;
                else l = mid;
            }
            
            if(str[i - l] <= 'z') res = max(res, l + 1);
            else res = max(res, l);
        }
        
        printf("Case %d: %d\n", T++, res);
    }
    
    
    return 0;
}

后缀数组

题目描述

后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者DC3算法实现，这超出了我们的讨论范围。
在本题中，我们希望使用快排、Hash与二分实现一个简单的O(nlog2n)的后缀数组求法。
详细地说，给定一个长度为 n 的字符串S（下标 0~n-1），我们可以用整数 k(0≤k<n) 表示字符串S的后缀 S(k~n-1)。
把字符串S的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。
额外地，我们考虑排名为 i 的后缀与排名为 i-1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。
我们的任务就是求出SA与Height这两个数组。
输入格式
输入一个字符串，其长度不超过30万。
字符串由小写字母构成。
输出格式
第一行为数组SA，相邻两个整数用1个空格隔开。
第二行为数组Height，相邻两个整数用1个空格隔开，我们规定Height[1]=0。
输入样例：
ponoiiipoi
输出样例：
9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

题解

先想出朴素做法：用一个下标表示字符串后缀的开头。然后使用快排对这些后缀排序。
比较函数：挨个字符比较。
求两个字符串的最长公共前缀长度，可以用字符串哈希的做法。即二分枚举最大长度，如何判断
这两个字符串是相同的呢？可以求出在这个长度下的字符串哈希值，通过比较哈希值，判断在这两个字符串是不是相同的字符串。
优化比较函数：可以先求出两个后缀的最大公共长度，然后比较最大公共长度后一个字符的大小即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>

using namespace std;
typedef unsigned long long ULL;
const int N = 300010, base = 131;
char str[N];
int sa[N];
ULL h[N], p[N];
int n;

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

//二分获取最大公共长度
int get_max_common_prefix(int a, int b)
{
    int l = 0, r = min(n - a + 1, n - b + 1);
    while(l < r)
    {
        int mid = l + r + 1>> 1;
        if(get(a, a + mid - 1) != get(b, b + mid - 1)) r = mid - 1;
        else l = mid;
    }
    
    return l;
}

//比较函数
bool cmp(int a, int b)
{
    int l = get_max_common_prefix(a, b);
    int av = str[a + l];
    int bv = str[b + l];
    return av < bv;
}

int main()
{
    scanf("%s", str + 1);
    
    n = strlen(str + 1);
    
    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * base + str[i] - 'a' + 1;
        p[i] = p[i - 1] * base;
        sa[i] = i;
    }
    
    sort(sa + 1, sa + n + 1, cmp); //排索引
    
    for(int i = 1; i <= n; i++) printf("%d ", sa[i] - 1);
    puts("");
    for(int i = 1; i <= n; i++)
    {
        if(i == 1) printf("0 ");
        else printf("%d ", get_max_common_prefix(sa[i - 1], sa[i]));
    }
    
    puts(" ");
    
    return 0;
}