字符串问题

字符串匹配

又称模式匹配，在文本串 S 中匹配长度为 len 的模式串 T ，即是否存在 S 的子串 str 满足 $str_i==T_i, \forall i\in [1, len]$

单模式串匹配

• 字符串哈希：预处理文本串和模式串的哈希值，在文本串上进行区间匹配。$O(n+m)$
• KMP算法：预处理模式串的前缀函数，在文本串上进行匹配。$O(n+m)$

多模式串匹配

• AC自动机：预处理所有模式串，在文本串上进行匹配。$O(\sum|T|+|S|)$

字典序问题

• 后缀数组

子串问题

单字符串

• 后缀自动机

多字符串

• 广义后缀自动机

回文问题

单字符串的最大回文串长度

• Manacher算法

单字符串的所有回文串

• 回文自动机

字符串哈希

实现

进制哈希

选择 B 进制，将字符串 $s[1, n]$ 通过哈希函数映射为 $f(s)=\sum_{i=1}^{n}s_i\times Base^{n-i}(mod MOD)$ ，要求 $Base,MOD$ 均质数。进制一般选大于字符集大小的值，如29、131、233、13331。

2种哈希方式：

• 单Hash
  • 自然溢出：unsigned long long 自动对 $2^{64}$ 取模
  • 大进制和大质数模数：模数选1e9+7、1e9+9、212370440130137957LL
• 双Hash
  • 采用不同的Base和MOD，进行两次单Hash，将结果作为二元组表示

不要把任意字符对应到数字0，一般从1开始。由于模数较大，一般使用 $map<ll, int>$ 或 $map<pair<ll, ll>, int>$ 存储哈希表。一般双哈希的时间是单哈希的2倍。

多次询问子串哈希

对整个字符串先预处理每个前缀的哈希值 $hash(s[1, i])=\sum_{j=1}^{i}s_j\times Base^{i-j}(mod MOD)$ ，即 $hash_i=(hash_{i-1}*B+s_i)%MOD$ 。

$hash(s[l, r])=\sum_{j=l}^{r}s[j]\times Base^{r-j}(mod MOD)=hash(s[1,r])-hash(s[1,l-1])\times Base^{(r-l+1)}$ 。

故子串 $s[l, r]$ 的哈希值为 $hash[r]-hash[l-1]*B[r-l+1]$ 。可 $O(n)$ 预处理 $B[r-l+1]$ 然后 $O(1)$ 回答每次询问。

template<int base,int mod>
struct Hash{
    int pw[1000010],hs[1000010];//幂数组、哈希值数组
    inline int get(int l,int r){//询问子串哈希
        return (hs[r]-1ll*pw[r-l+1]*hs[l-1]%mod+mod)%mod;
    }
    inline void init(const string& s, int n){//初始化字符串哈希
        pw[0]=1;
        for(int i=1;i<=n;i++) pw[i]=1ll*base*pw[i-1]%mod;
        for(int i=1;i<=n;i++) hs[i]=(1ll*hs[i-1]*base+s[i])%mod;
    }
};
Hash<233,int(1e9+7)> s1,t1;//双哈希：不同进制+不同模数
Hash<241,int(1e9+9)> s2,t2;

哈希+二分

哈希匹配具有单调性，若两个字符串前 x 个字符可匹配，则前 x-1 个字符也可匹配；若前 x 个字符不可匹配，则前 x+1 个字符也不可匹配。

思想

• 将输入映射到一个值域较小、方便比较的范围，即将字符串映射为整数
• 由生日悖论，选择模数 mod，则 $\sqrt{mod}$ 个串就大概率会哈希碰撞

应用

字符串匹配

求模式串哈希值，求出文本串每个长度为模式串长度的子串的哈希值，分别与模式串哈希值比较即可。

允许 k 次失配的字符串匹配

问题：允许最多有k个位置字符不同，求文本串 S(n) 中有多少子串与模式串 T(m) 匹配。

哈希+二分。枚举所有可能匹配的子串，通过哈希+二分 $O(log_2m)$ 找到首个失配位置，删除子串和模式串在此及之前所有部分，继续查找下一个失配位置。

$O(m+knlog_2m)$

inline ll getHash(ll* hash, int l, int r){//查询子串哈希值
    return (hash[r]-hash[l-1]*bb[r-l+1]%MOD+MOD)%MOD;
}
int lcp(int x, int y, int r){//二分哈希匹配最长前缀长度
    int l=1, mid, res=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(getHash(hash1, x, x+mid-1)==getHash(hash2, y, y+mid-1)){
            res=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return res;
}
bool check(int x, int k){//从文本串第x个字符开始允许k次失配的字符串匹配
    int r=x+m-1, y=0;
    for(int i=0; i<k; ++i){
        int len=lcp(x, y, m-y);//二分失配位置
        x+=len+1;
        y+=len+1;
        if(y>=m) return 1;//匹配完成
    }
    return getHash(hash1, x, r)==getHash(hash2, y, m-1);
}

最长回文子串

记 $R_i$ 表示以 i 结尾的最长回文的长度，答案为 $max_{i=1}^nR_i$ 。由于 $R_i\leq R_{i-1}+2$ ，只需暴力从 $R_{i-1}+2$ 开始递减直到找到首个回文即可。

$O(n)$

unsigned long long gethash1(int l, int r)
{
    return order1[r] - order1[l - 1] * pwd[r - l + 1];
}
unsigned long long gethash2(int l, int r)
{
    return order2[l] - order2[r + 1] * pwd[r - l + 1];
}
int main()
{
    pwd[0] = 1;
    for (int i = 1; i <= 1000000; i++)
        pwd[i] = pwd[i - 1] * base;
    int CASE = 1;
    while (~scanf("%s", s))
    {
        if (!strcmp(s, "END"))
            break;
        printf("Case %d: ", CASE++);
        int len = strlen(s);
        ct = 1;
        s2[ct++] = '#';
        for (int i = 0; i < len; i++)
        {
            s2[ct++] = s[i];
            s2[ct++] = '#';
        }
        len = ct - 1;

        order1[0] = order2[len + 1] = 0;
        for (int i = 1; i <= len; i++) //正哈希
            order1[i] = order1[i - 1] * base + s2[i];
        for (int i = len; i >= 1; i--) //逆哈希
            order2[i] = order2[i + 1] * base + s2[i];

        int maxx = 0;
        for (int i = 1; i <= len; i++) //On求最长回文子串
            while (i - maxx >= 1 && i + maxx <= len &&
                   gethash1(i - maxx, i + maxx) == gethash2(i - maxx, i + maxx))
                maxx++;

        printf("%d\n", maxx - 1);
    }
    return 0;
}

最长公共子字符串

问题：m个总长不超n的非空字符串，求所有字符串的最长公共子字符串。

哈希+二分。二分最长公共子字符串的长度，假设当前长度为 k ，check(k) 将所有所有字符串的长度为 k 的子串分别进行哈希，将哈希值放入字符串总长个哈希表中存储。之后求交集即可。

$O(m+nlogn)$

确定字符串中不同子字符串的数量

问题：求长度为 n 的字符串中不同子串的数量

哈希，然后遍历所有子串哈希值，将子串哈希值存入集合，集合大小即答案。

$O(n^2)$

字符串比较

哈希+二分实现 $O(logn)$ 比较字符串

前缀函数

实现

• 前缀函数 $nex_i$ 表示子串 $s[1, i]$ 中最长且相等的真前缀和真后缀长度
• 设置失配指针 k，失配后跳转 $nex_k$ 到 $s[1, i]$ 中更短的公共前后缀，递推寻找合适长度的公共前后缀

思想

$nex_i, nex_{nex_i}…$ 都是前缀串 $s[1, i]$ 的公共前后缀，且只有它们是公共前后缀

应用

• KMP算法
• 字符串的周期 ：从小到大为 $n-nex_i$、$n-nex_{nex_i}…$

KMP算法

实现

算法流程：

1. 求模式串的前缀函数
2. 对文本串进行匹配

思想

利用公共前后缀的特性，采用最优历史处理，失配后跳转到更小的公共前后缀而非从头开始匹配，减少重复匹配次数

应用

KMP算法可视作KMP自动机，基于模式串的KMP自动机接受且仅接受以模式串为后缀的文本串，解决单模式串匹配问题。

单模式串匹配

$O(n+m)$

int nex[N], num[N]
char t[N], p[N];
void getNext(int n)
{
    int k=0;
    num[1]=1;
    for(int i=2; i<=n; ++i)
    {
        while(k>0 && p[i] != p[k+1]) k=nex[k];
        k+=(p[i]==p[k+1]);
        nex[i]=k, num[i]=num[k]+1;//递推记录从i跳转到0需要几次，实际上就是从0长度到nxt[i]长度的字符串有几个
    }
}
void KMP()
{
    int plen=strlen(p+1);
    int tlen=strlen(t+1);
    getNext(plen);
    int k=0;//k表示当前匹配的长度，即失配指针
    for(int i=1; i<=tlen; ++i)
    {
        /*text和pattern不匹配，且k>0，表明text和patt有部分匹配，向更小的公共前后缀匹配*/
        while(k>0 && p[k+1]!=t[i]) k=nxt[k];
        k+=(p[k+1]==t[i])
        if(k == plen)//k移动到pattern末端
        {
            cout<<i-plen+1<<endl;//输出位置
            k=nxt[k-1];/*重新初始化，寻找下一个，++i后，下一次模式字符串的开头在i-nxt[k-1]+1处*/
            //return i-plen+1;
        }
    }
}