10.6课堂笔记

清北学堂 笔记

RK-hash：

把一个字符串看作一个base进制的大整数，然后对一个大素数p取模
hash[i]=(hash[i-1]*base+s[i])%p

base可以取大于|∑|的数
注意不要把任何字符映射为0

p一定要是long long 范围内的一个素数，如：
23333333333333333,1e18+9（不建议用，一般用一个1e15左右的数就可以了）等

unsigned long long自然溢出可以看作是对2^64位取模，并且这个很快
不过会被特殊构造的数据卡掉（看出题人心情……）

如果不放心可以多找几个素数同时算

求任意一段的hash值

如果要求l~r的hash
首先求1~r的hash
然后求1~l-1的hash
hash[r]-hash[l-1]*pow(base,r-l+1)

两个hash值合并：

A B
hash[A]=123,hash[B]=456
hash[A]+hash[B]=123000+456=123456

用素数的原因：

hash冲突的可能性较小

用hash值求两个字符串之间的最长公共前缀（LCP）

hash%(10*k) k=1~min(len(A),len(B))

用hash值判断两个字符串字典序的大小

哈希表：

存储hash值的数据结构
hash[i][j]里面存的是这个字符串的编号
i、j表示这个字符串的hash值%p的结果为i的第j个字符串

XOR版本的RK-hash

hash[i]=(hash[i-1]*base ^ s[i])%p
中间的^表示异或，这个版本与加法版本相比，不太容易被卡
但是加法版本的可以用前缀和

例题：bzoj3555企鹅qq

Description

PenguinQQ是中国最大、最具影响力的SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。
小Q是PenguinQQ网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q发现同一个人注册的账户名称总是很相似的，例如Penguin1，Penguin2，Penguin3……于是小Q决定先对这种相似的情形进行统计。
小Q定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。而小Q想知道，在给定的 个账户名称中，有多少对是相似的。
为了简化你的工作，小Q给你的 个字符串长度均等于 ，且只包含大小写字母、数字、下划线以及‘@’共64种字符，而且不存在两个相同的账户名称。

Input
第一行包含三个正整数n，m，k。其中n表示账户名称数量，m表示账户名称长度， k用来表示字符集规模大小，它的值只可能为2或64。
若k等于2，账户名称中只包含字符‘0’和‘1’共2种字符；
若k等于64，账户名称中可能包含大小写字母、数字、下划线以及‘@’共64种字符
随后n行，每行一个长度为m的字符串，用来描述一个账户名称。数据保证n个字符串是两两不同的。

Output
仅一行一个正整数，表示共有多少对相似的账户名称。

Sample Input
4 3 64
Fax
fax
max
mac

Sample Output
4

HINT
4对相似的字符串分别为：Fax与fax，Fax与max，fax与max，max与mac。N<=30000,L<=200,S<=64

解法：
枚举删去某一位。然后hash表，排序之类的

KMP

KMP是一个常用的单模式串匹配算法，时间复杂度O(len(匹配串))
单模式串匹配问题：
一个主串（匹配串），一个子串（模式串），询问子串在主串中出现了多少次、分别出现在哪里

朴素算法是枚举每一位，两两比较，如果发下有不一样的就从下一位开始重新匹配

KMP算法：

洛谷KMP版子题
https://www.luogu.org/problem/show?pid=3375

引入一个next数组
next是对子串的处理
next[i]表示当结尾为i的时候最长的字符串后缀等于字符串前缀的长度
自己匹配稍短一些的自己
匹配失败的时候子串从next[失败的位置]开始
举例：
子串:ababcab
next:0012012

子串:ababab
next:001234

int Next[1000];
int len1,len2;
string s1,s2;
void getNext()
{//子串的处理
    Next[0]=Next[1]=0;
    for(int i=1;i<len2;i++)
    {
        int j=Next[i];
        while(j&&s2[i]!=s2[j])
            j=Next[j];
        if(s2[i]==s2[j])
            Next[i+1]=j+1;
        else    Next[i+1]=0;
    }
    return;
}
void KMP()
{//子串处理完之后匹配子串和主串
    int j=0;
    for(int i=0;i<len1;++i)
    {
        while(j&&s1[i]!=s2[j])j=Next[j];
        if(s1[i]==s2[j])++j;
        if(j==len2)//假设题目要求输出每个匹配的串的位置
            printf("%d\n",i-len2+2);
        //此处不进行j的清零以尽快找到下一个匹配的串的位置 
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>s1>>s2;
    len1=s1.size();
    len2=s2.size();
    getNext();
    KMP();
/*
对于Next数组的输出
    for(int i=1;i<=len2;++i)//从1开始是因为getNext中主要是对Next[i+1]进行操作
        printf("%d ",Next[i]);
*/
    return 0; 
}

KMP的应用：
单模式串匹配
求串的循环节

Manacher算法

对称思想、能不做的东西都不做
通过字串的对称性简化求结果的过程
对于求回文串问题
hash+二分可以O(nlogn)求出答案
manacher可以O(n)地求出每个位置的回文半径，即以这个位置为中心的回文串的长度的一半
方法：
通过加字符，只考虑奇数长度回文串
如果是偶数长度怎么半？
在字符串中的字符两两之间添加特殊字符，那么任意一个回文串都一定是奇数长度回文串
另外在字符串首端、尾端各添加一个不一样的特殊字符

int mx=max{i+r[i]-1}
int id mx取到最大值时的i
//r[i]表示i为中心的回文半径
for(int i=1;i<=l;++i)
{
    r[i]=min(r[id-(i-id)],mx-i);
    while(s[i-r[i]]==s[i+r[i]])++r[i];
    if(i+r[i]-1>mx)
    {
        mx=i+r[i]-1;
        id=i;
    }
}

推论：
每个字符串之中本质不同的回文串最多O(n)个

例题：BZoj2342双倍回文
定义 双倍回文 为 一个回文串套一个回文串， 问一个串中的最长双倍回文串。
做法：已知一个字符串之中最多O(n)个本质不同的回文串
所以枚举每一个本质不同的回文串，判断是不是双倍回文即可

也可以在manacher的过程中搞一下

例题二：BZoj3676回文串
用manacher找出本质不同的回文串，每个串在后缀自动机上查询出现次数
或者回文树……
不知道回文树的戳这里->Palindromic Tree

exKMP

思想与manacher类似
先求模式串的每个后缀和自己的LCP

暴力写法
for(int i=1;i<=n;++i)
{
    p[i]=0;
    while(b[i+p[i]]==b[p[i]+1])++p[i];
}
可以二分优化为O(log(n))

exKMP写法：
for(int i=1;i<=n;++i)
{
    p[i]=min(mx-i);
    while(b[i+p[i]]==b[p[i]+1])++p[i];
    if(i+p[i]>mx)
    {
        id=i;
        mx=i+p[i];
    }
}
时间复杂度同manacher，O(n)
两个串之间求LCP，思想同自己和自己的匹配

例题：tyvj1068STR
思路：exKMP

字典树（Trie树）

int trie[100000][26];
int tot;
//root=0;
void insert(char *s)
{
    int p=0;
    for(int i=0;s[i];++i)
    {
        if(trie[p][s[i]-'a')id=trie[p][s[i]-'a';
        else    id=trie[p][s[i]-'a']=++tot;
    }
    ++flag[p];//记录结束的节点有多少
}

用处：求多个字符串的字典序排序
顺便帮xxy学姐打个广告浅谈Trie树

AC自动机（Trie图）

把Trie 树上不存在的孩子用它fail 节点的孩子补出来。
fail节点的作用与KMP的next数组类似
理论上，如果不会KMP的话可以用单串AC自动机替代

例题1：hdu2222
求多模式匹配串问题

bzoj2938病毒
在Trie图上把病毒代码段删掉，如果存在一个环，那么存在一个无限长的安全代码段，输出“TAK”
如果不存在一个环，那么输出“NIE”

bzoj1030文本生成器
bzoj3764Petya的序列