最小表示法，字符串哈希

最小表示法

给出字符串 $S$ ，在其所有的循环同构串中选择字典序最小的一个串

循环同构：当字符串 $S$ 中可以选择一个位置 $i$ ，满足 $S_{i,n}+S_{1,i-1}=T$ 那么记 $S,T$ 循环同构

可以利用类似双指针的办法解决

构造字符串 $\hat{S}=S+S$ ，设立两个指针 $u,v$

例如： $S=b\ c\ a\ d\ a\ b\ d\ d$ ，$\hat{S}=b\ c\ a\ d\ a\ b\ d\ d\ b\ c\ a\ d\ a\ b\ d\ d$

一开始 $u=1,v=2$ 设前 $k$ 个字符相同，当 $\hat{S}_{u+k}\ne \hat{S}_{v+k}$ 时，指针可以移动

$\hat{S}_{u+k}> \hat{S}_{v+k}$ 说明以 $u$ 为开始的循环同构串字典序大于以 $v$ 开始的，那么移动 $u=u+k+1$
$\hat{S}_{u+k}< \hat{S}_{v+k}$ 说明以 $v$ 为开始的循环同构串字典序大于以 $u$ 开始的，那么移动 $v=v+k+1$

因为 $\hat{S}_U$ 与 $\hat{S}_V$ 前 $k$ 个字符相同，说明字典序相同，那么下一次判断可以跳过这段重复的区间

如果 $\hat{S}_{u+k}= \hat{S}_{v+k}$，说明可以增加 $k$ 区间长度，即 $k+1$

string s;
cin>>s;
int n=s.size();
s="0"+s+s;//0占位符，规范下标从1开始

int u=1,v=2,k=0;
while (u<=n&&v<=n){
    for (k=0;k<n&&s[u+k]==s[v+k];k++);
    if (s[u+k]>s[v+k]) u+=k+1;
    else v+=k+1;//相等的情况前面循环已排除
    if (u==v) u++;
}

最后的答案 $ans={\rm{min}}(u,v)$ ，这是因为在

if (s[u+k]>s[v+k]) u+=k+1;
else v+=k+1;

过程中，如果 $u,v$ 向后移动超过了 $n$ 的范围就会立刻终止循环，又因为 $[n+1,2n]$ 的区间与 $[1,n]$ 区间完全一致

那么在 $n$ 后位置上确定的循环同构串已经在 $n$ 前判断过，所以输出 $u,v$ 最小者即可

字符串哈希

给定许多字符串，判断其中是否存在重复的串

如果暴力判断会浪费许多时间在字符串的匹配上，这时候可以利用哈希函数将这个字符串映射为一个数值

映射后不同的数值对应的原字符串一定不相同，相同的数值对应的原字符串不一定相同

显然，我们肯定是理想让不同字符串映射后的数值都不相同，（相同称为哈希冲突）

首先是字符串常用的哈希方式：模数哈希

每个字符串的每个字符都对应一个 ASCII 码，天然可以映射为一个数字，那么对于长为 $n$ 的字符串 $S$ ，定义它的模数哈希函数为

$$ hash=(S_1*B^{n-1}+S_2*B^{n-2}+\cdots+S_{n-1}*B^1+S_{n}*B^0)\ {\rm{mod}}\ M $$

其中的 $B$ 表示 $B$ 进制，将整个字符串视为一个 $B$ 进制的数，整个多项式对 $M$ 取模

一般的，$B$ 常取 $131,13331,13131$ ，$M$ 常取 $2^{32}-1=212370440130137957,10^9+7,19260817$

const ULL HashBase=13331;
const ULL HashMod=212370440130137957;

ULL hash(string s){
    int len=s.size();
    ULL res=0;
    for (int i=0;i<len;i++) 
        res=(res*HashBase+(ULL)s[i])%HashMod;
    return res;
}

估测哈希冲突的概率函数计算：哈希空间 $M$ 下插入 $k$ 个字符串的冲突概率，$M$ 与模数定义相同

$$ p(k,M)=1-e^{-\frac{k(k-1)}{2M}} $$

但是，这样的计算出来的哈希冲突概率仍然较高，可能会被卡

所以可以利用双值哈希的操作，将哈希冲突的概率降低到

$$ p(k,M)^2=\left[ 1-e^{-\frac{k(k-1)}{2M}} \right]^2 $$

即采用两个不同的哈希函数映射，当且仅当两个字符串的两个哈希值完全相同时才视作相同

const ULL HashBase=13331;
const ULL HashMod_1=212370440130137957;
const ULL HashMod_2=1e9+7;

ULL hash_1(string s){
    int len=s.size();
    ULL res=0;
    for (int i=0;i<len;i++) 
        res=(res*HashBase+(ULL)s[i])%HashMod_1;
    return res;
}

ULL hash_2(string s){
    int len=s.size();
    ULL res=0;
    for (int i=0;i<len;i++) 
        res=(res*HashBase+(ULL)s[i])%HashMod_2;
    return res;
}

最小表示法，字符串哈希

阅读选项