「总结」 字符串总结

字符串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;
}

亲测没有什么问题

后缀数组

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