字符串总结

学习笔记 题单

字符串Hash

Hash还是很简单的,随便写点东西吧.

普通Hash

直接自然溢出就好了,大致代码如下:

#define ull unsigned long long
ull Hash[3000010];
const ull base=19260817;
void init(char *s)
{
    for(int i=0;i<strlen(s);i++)
        Hash[i]=Hash[i-1]*base+s[i];
}
#undef

这个Base你可以自己随便写一些东西...

双模数Hash

一般性就是取一些什么$Mod1=1e9+7$,$Mod2=998244353$之类的..

如果你实在是特别喜欢自然溢出,可以和我一样一个用$unsigned\ int$,另一个用$unsigned \ long\ long$,这个也相当于是有两个模数...但是后面那个并不是质数(不过这个没什么用,一样的搞就好了.)

卡Hash

详情参见 Hash Killer的Solution(咕咕咕)

KMP

这个东西很好理解,所以还是背背板子理解一下的好.
考虑我们令$nxt_i$表示$1$~$i$之间的最长公共前后缀.
如果我们匹配到某一个位置无法匹配,就跳一下$nxt$就好了.
具体来说这个东西很玄学:(下面是30s口胡过程)
因为现在我们是第$i$为无法与$j$匹配,所以我们要找一个可以匹配的$j$或者是不匹配了.
那么如果长度减了之后,显然在i串上面形如一段后缀,在j上面形如一段前缀,然后这个定义的来由就差不多讲清楚了.

那么怎么求呢?直接把模式串与模式串匹配就好了.相当于是在模式串里面找模式串.

AC自动机

今天才学(3.27),以前好像学过,但是没学懂...

考虑如果有很多个模式串,单文本串匹配怎么办呢?
我们把模式串丢到一个$Tire$Trie树上面去.
那么剩下的过程就是解我们的nxt数组了对吧.
这个东西直接跑一个bfs求解就好了.
自己画画图分析,应该就没错了.

manacher

这个东西是求一个串的最长回文子串，比较容易就不写了。
$p_i$表示以$i$为回文中心的最长回文半径，这个东西暴力搞。
复杂度正确的原因是：
1. 一个串最多有线性个本质不同的回文串。
2. 只有当出现不同的本质不同的回文串，$p$才会后移。

后缀自动机

怕不是我写过的最多的字符串题吧.谢罪了
这个构建自己随便yy一下就好了,大致流程参考$yyb$的Blog...
放一个extend的模板(主要是怕自己忘了)

void extend(int c)
{
    int np=++tot,p=last;last=tot;
    t[np].len=t[p].len+1;
    while(p && !t[p].son[c])t[p].son[c]=np,p=t[p].ff;
    if(!p)t[np].ff=1;
    else
    {
        int q=t[p].son[c];
        if(t[p].len+1==t[q].len)t[np].ff=q;
        else
        {
            int nq=++tot;
            t[nq]=t[q];t[q].ff=t[np].ff=nq;
            t[nq].len=t[p].len+1;
            while(p && t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
        }
    }
    siz[np]=1;
}

亲测没有什么问题

后缀数组

难道我要说不会?好像确实是的...
大概背个模板就差不多了.
给出模板!!
代码戳这里

最小/大表示法

把串复制一遍放到末尾,然后建后缀自动机,在上面跑n次就好了.
你问线性的?(当然会啦)
考虑我们定义两个指针$i,j$分别指向$a_1,a_2$,定义$k$表示匹配的长度,那么对于:$i+k-1\%n+1$和$j+k-1\%n+1$这样子的两个位置,显然有如下三种情况:

1. a[(i+k-1)%n+1] = a[(j+k-1)%n+1],k++.
2. a[(i+k-1)%n+1] < a[(j+k-1)%n+1],显然j不优,那么就把j跳到$j+k$,k=0.
3. a[(i+k-1)%n+1] > a[(j+k-1)%n+1],显然i不优,那么就把i跳到$j+i$,k=0.

然后这个东西就做到比较快的了.

回文自动机

自动机里面除了AC自动机之外最简单的吧.
考虑回文串有两种,一个是奇数长度的,另一个是偶数长度的.
回文自动机上面的节点应该代表着是两个字符,如:
$aba$->$c$->$cabca$
那么我们如果要在回文自动机跑东西怎么办呢?
考虑令$fail_i$表示以$i$结尾的最长的回文后缀(不包括自己).
那么每加入一个节点,只要和上一次的比一下是否匹配就好了.
接着考虑插入这一个字符,如果存在就不要管对吧.
不存在怎么做?
从$last$的祖先中找一个可以匹配的上的回文串就好了.
长度每一次是+2.
具体代码可以到我的cnblogs内查看.