字符串问题选讲

# 省流：本篇专供冲击NOIP一等的人使用，坐标HN

# 1.字符串hash

这个可以说是最简单的字符串算法了

其实这个没什么特别的，有选手用离散化~~乱搞都可以过~~

英文中$hash$的本意是“打乱”（为什么不用$shuffle$），但OI中就没有也不可能有让你把某种数据打乱的问题

这里的$hash$就是一种**相关关系**（作为半$whker$，我觉得这么说也合适），能够将**某种数据**（int、string、struct，对，自定义的结构体）转换成**存储位置下标**（数组、链表都可以）。那这怎么转换呢？

我们考虑：对字符串的每一个字符，比如说$hash$,它可以看成由$h、a、s、h$按顺序排列的$len$位数，其中$len$为字符串长度

一个很自然的想法是把一个字符串看成一个大进制数（多大呢？在char（ASCII）环境下，你总得比127大一点吧，不然怎么表示每个字符呢），然后把这个字符串按照这个进制处理成一个数，然后就得到下标了。

然而，当字符串一长，长到比$long$ $long$甚至比我不爱用的$int128$能表示的范围还长的时候，你就寄了，因为放不下，没有这么大的下标。对于这种情况，%%%是一个很好的做法(bushi)，我们只要对一个足够大的质数取模就行了

记字符串$s$可看为$base$进制，对$p$取模，字符串的每一个字符（从左到右和从右到左好像没有关系）那么$hash$操作可表示为
$$hash[s]=(\sum_{i=0}^{len(s)}hash[i-1]*base+s[i]) \bmod p$$

（为防止求和符号导致理解误会，我习惯施加一点括号，请见谅）

对于这个$hash$操作，你既可以使用**数组**记录$hash[i]$，也可以使用$ans$**变量**直接记录结果，注意到这个数字肯定非常大

> 十年OI一场空，不开$long$ $long$见祖宗

但是你的$p$只有$int$那就没事了（

这里的$base$和$p$都可以自己定。因为$string$的每一位为$char$，依据$ASCII$只有$128$个字符的实际情况，我们一般把$base$定为$131$，$p$的话，你自己随便定，完全可以定成某人生日（乐）。而且只要取得足够大，它是不是质数问题实测不是很大。

有一种模数比较简单，它让我们只使用$unsigned$ $long$ $long$记录结果，这样就相当于对$2^{64}$%%%。但出题人已经找到了成熟的卡这种“自动取模”或“自然溢出”的数据特性，所以当你决定图省事时，~~你一定要想一下该比赛的出题人喜不喜欢拿脚造数据~~

~~当出题人是lxl级别的时候，窃以为你还是不可以总司令的好~~

比如说我是前锦依卫、忠实的御绫军，我的模数就喜欢取$2012071212$或$201504129$，诶，就是这个味儿。希望天依和阿绫祝我rp++（$bushi$）

当两个字符串的**hash值相同**时，我们就认为它们是相等的。

但也有种情况，不知道你们有没有玩过Grand Theft Auto，它的作弊码在III和Vice City里都是按**实际值**存储的，所以可读性很高。但San Andreas这一部里，有一些作弊码看上去莫名其妙，~~对英语考试增益为0~~，这就是和开发人员规定的作弊码hash值碰巧相同的字符串，而San Andreas里，作弊码恰好以**hash值**存储，就闹了乌龙

我们可以论证这种问题，按$p$取模，一个hash表最多只可能有$p$种结果，碰撞率很低，但还不能近似为$0$。~~而且不知道为什么题目就这么容易把碰撞卡出来，甚至卡的死死的~~

但是，一次不行，我们$hash$两次。再多，$O(1)$的常数就大出天际了。

对于双$hash$，我们只要写两个函数，同时用两个模数取模运算结果就行了，~~同时宠爱天依和阿绫真是太爽了~~

对于$n$个模数，每个模数的结果的结合遵从**乘法原理**（分步%%%），所以就可能有$\prod^{n}_{i=1}$种结果，这个基本上已经超出绝大部分算法竞赛的题所给出的数据规模了，因此，对于多重hash，我们可以认为它不会发生碰撞。

值得一提的是，对于单/多hash，€€￡的官方教材上给出的结果数为$\sqrt p$和$\sqrt{\prod^{n}_{i=1}p_{i}}$，这一定要查证一下。

我们把两个hash的结果看成一个二元组/二维向量，字符串相等，就是这两个hash值对应相等。

还有所谓 **“开放定址法”** 和 **“挂链法”**，这个我是之前在工程领域见到的，OI似乎用的不多（也许数的哈希会常用？），我们就不做要求了。

## 习题1

[P3370 【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370)

上面讲的差不多了，你可以动手试试

请你注意题面的提醒：

> 友情提醒：如果真的想好好练习哈希的话，请自觉。

不要一个$map$呼上去，~~这又不是排序的模板~~，也不要用离散化之类的其他算法~~乱搞~~，学hash，就好好用hash

AC Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+7;
const int maxm=1.5e3+10;
const int p=131;
const ll mod1=201504129;
const ll mod2=2012071212;

int idx(char c)
{
	return (int)c;
}

struct data
{
	ll x;
	ll y;
	
	friend bool operator <(data a,data b)
	{
		return a.x<b.x;
	}
};
data hashres[maxn];

void hashe1(int pos,string s)
{
	ll ans=0;
	int len=s.size();
	for(int i=0;i<len;i++)
	{
		ans=(ans*p+(ll)s[i])%mod1;
	}
	hashres[pos].x=ans;
}

void hashe2(int pos,string s)
{
	ll ans=0;
	int len=s.size();
	for(int i=0;i<len;i++)
	{
		ans=(ans*p+(ll)s[i])%mod2;
	}
	hashres[pos].y=ans;
}

int main()
{
	int n=0,res=1;
	string s;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		hashe1(i,s);
		hashe2(i,s);
	}
	sort(hashres+1,hashres+n+1);
	for(int i=2;i<=n;i++)
	{
		if(hashres[i].x!=hashres[i-1].x&&hashres[i].y!=hashres[i-1].y)res++;
	}
	cout<<res;
	return 0;
}
```

**如果你想研究子串问题，强烈建议用$hash$数组法通过此题，因为你可以使用差分$O(1)$求子串是否相等，切记！**

# 2.字典树/Trie

字典树讲白了就是把字符串丢到树上排列，把插入（存储）和查询变得更快，而且支持把相同的前或后缀重叠在一起，省空间。本文主要讲解前缀trie。

讲的轻松，怎么做呢？

我们把每个字符串的每个字符看作一个树的节点之间的边，并且照例还是$idx$表示当前点数。

然后我们开个结构体，结构体里面存什么呢？存一张地图

？？？

是这样的，请看VCR！

```cpp
struct trie
{
  int children[maxn][charset];
  int cnt[maxn];
}
```

其中，$maxn$表示总共会有多少个字符（所有插入的句子加起来），$charset$是字符集的大小。只有小写字母时就是$26$，大小写加字母就是$62$等等。我们把一个字符作为一个节点，哦，那怎么表示标点符号呢？把单词都塞进来，到时候就区分不出了QAQ还怎么查找？$cnt$就是解决这个问题的。当我们插入完了一个单词，我们就在最后一个字符节点在$cnt$中的位置赋1，以表示结束，当然，还可以++表示出现了多少次，两种的插入函数差异甚至特别小（

好，有了结构，我们怎么实现插入和查询呢？

我们的插入函数接受一个字符串作为参数，每个字符放入trie的每一层。我们默认从第0层开始，然后对于插入字串的每个字符，我们先判定它是哪条边，如果当前节点还没有这条边，我们就把它添加进来，并把它的另一个节点设定为新节点（即$++idx$）。同时，我们给这个结点的$cnt$加一。

举个例子啊！假设插入这两个字符串：

```plain text
aity
aialing
```

过程如下：

- 对于第一个串：

- 插入a，第0个节点没有一条a的边往下走，新建一条a的边，分别连接$id=0$和$id=1$两个节点，$cnt[1]++$

- 插入i，第1个节点没有i的边，新建一条，分别连接$1$和$2$两个节点，$cnt[2]++$

- 插入t，第2个节点没有t的边，新建一条，分别连接$2$和$3$两个节点，$cnt[3]++$

- 插入y，第3个节点没有y的边，新建一条，分别连接$3$和$4$两个节点，$cnt[4]++$

- 第一个串插完了，对于第二个串，我们依然从最顶上插起：

- 插入a，诶，第0个节点有a的边了，直接往下走，笑死

- 插入i，诶，第1个节点有i的边了，直接往下走，笑死

- 插入a，第2个节点没有a的边，此时$id=4$，那我们新建一条，分别连接$2$和$5$两个节点，$cnt[5]++$

- 插入l，第5个节点没有l的边，新建一条，分别连接$5$和$6$两个节点，$cnt[6]++$

- 插入i，第6个节点没有i的边，新建一条，分别连接$6$和$7$两个节点，$cnt[7]++$

- 插入n，第7个节点没有n的边，新建一条，分别连接$7$和$8$两个节点，$cnt[8]++$

- 插入g，第8个节点没有g的边，新建一条，分别连接$8$和$9$两个节点，$cnt[9]++$

- 好，第二个串也存完了，收工。

当然，我们也可以把整个串全部插完以后，给最后一个节点打上$cnt$，两种做法适配不同的问题。

整个过程如下所示：
```cpp
void trie::insert(string s)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		int letter=getnum(s[i]);//这个函数要自己写，根据字符集来写（
		if(children[p][letter]==0)children[p][letter]=++id;
		p=children[p][letter];
		cnt[p]++;//就是这一句，也可放在循环之外。
	}
}
```

那查询怎么做呢？我们也是从根节点开始，沿着字符串每一个字母的边搜下去，如果在某一条字母边通向了空节点，即$0$，那就说明这个字符串不存在！最后，我们只要把最后访问到的点的$cnt$返回，就说明我们找到串了！（其实真正找到完全相同的串还要判一下完成标记，直接返回$cnt$只能保证是你传入的字符串是某个存在的串的前缀，当然，这两个也是针对不一样的问题的）

好了，现在我们就了解了$trie$的两个基本操作，我们就拿$\mathrm{I_2}$(bushi)开刀。

### 习题2.1.1

[P8306 【模板】字典树](https://www.luogu.com.cn/problem/P8306)

这题求的是一个查询字符串是多少个插入字符串的前缀，很显然要写每个节点都++的$insert()$，不然前缀无法统计到。

我们把所有插入字符串都插入进去，然后再一个个跑查询字符串，每个$find()$的返回值就是答案。

AC Code：

```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+7;

int getnum(char x)
{
	if(x>='A'&&x<='Z')
	{
		return x-'A';
	}
	else if(x>='a'&&x<='z')
	{
		return x-'a'+26;
	}
	else
	{
		return x-'0'+52;
	}
}
int id=0;

struct trie
{
	int children[maxn][63];
	int cnt[maxn];
	
	void insert(string s);
	int find(string s);
};
trie tries;

void trie::insert(string s)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		int letter=getnum(s[i]);
		if(children[p][letter]==0)children[p][letter]=++id;
		p=children[p][letter];
		cnt[p]++;
	}
}

int trie::find(string s)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		int letter=getnum(s[i]);
		if(children[p][letter]==0)return 0;
		p=children[p][letter];
	}
	return cnt[p];
}

inline void clean()
{
	for(int i=0;i<=id;i++)
	{
		for(int j=0;j<=62;j++)
		{
			tries.children[i][j]=0;
		}
	}
	for(int i=0;i<=id;i++)
	{
		tries.cnt[i]=0;
	}
	id=0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=0,n=0,m=0;
	string s;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		clean();
		cin>>n>>m;
		for(int j=1;j<=n;j++)
		{
			cin>>s;
			tries.insert(s);
		}
		for(int j=1;j<=m;j++)
		{
			cin>>s;
			cout<<tries.find(s);
			if(j<m)cout<<endl;
		}
		if(i<t)cout<<endl;
	}
	return 0;
}
```

关于另外一种$insert()$写法的例题，这里也讲一道，~~不然为什么叫$\mathrm{I_2}$呢~~

## 习题2.1.2

[P2580 于是他错误的点名开始了](https://www.luogu.com.cn/problem/P2580)

这个字符串查询肯定是要求**完全匹配的**（只找个前缀很有可能会找错人并且被校长欧拉欧拉欧拉）

那我们就只在每个插入字符串的末尾节点加$cnt$，作结束标识用，然后我们仍然根据返回值来判断，但是这里有点小麻烦，我们原来的$insert()$只给了一个数据，但我们会查询多次，我们必须在查询函数里手动加上“已点过”这个标记。

当然要省事可以`map<string,int>vis`，查询一个串，有，就打标记，但是这样空间很大，不是很优。但是在$find()$内改不是很行，主要是返回语句后就无法再修改值了，加完再返回又会错误地+1。

你也可以把判断条件都+1，但是我的解决方案是：

- $find()$不再返回值，改成`void`

- 原先要收留返回值的变量以**引用**形式传入

- 我们先改引用变量，然后再自增$cnt$

- main内根据引用变量的值为$0,1,\ge 2$输出`WRONG`,`OK`,`REPAET`

这样空间占用就小了，而且代码逻辑也没大改，很好。

给出这种方法的代码：

AC Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;

int getnum(char x)
{
	if(x>='A'&&x<='Z')
	{
		return x-'A';
	}
	else if(x>='a'&&x<='z')
	{
		return x-'a'+26;
	}
	else
	{
		return x-'0'+52;
	}
}
int id=0;
map<string,int>vis;

struct trie
{
	int children[maxn][63];
	int cnt[maxn];
	
	void insert(string s);
	void find(string s,int &x);
};
trie tries;

void trie::insert(string s)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		int letter=getnum(s[i]);
		if(children[p][letter]==0)children[p][letter]=++id;
		p=children[p][letter];
	}
	cnt[p]++;
}

void trie::find(string s,int &x)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		int letter=getnum(s[i]);
		if(children[p][letter]==0)
		{
			x=0;
			return;
		}
		p=children[p][letter];
	}
	x=cnt[p];
	cnt[p]++;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=0,m=0;
	string s;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		tries.insert(s);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		int res=0;
		tries.find(s,res);
		if(res==0)cout<<"WRONG";
		else cout<<((res==1)?"OK":"REPEAT");
		if(i<m)cout<<endl;
	}
	return 0;
}
```

# 咕咕咕，下面实在无法理解了（

# 3.KMP算法

如果你先前了解过字符串全家桶，你就会发现上述两个算法差不多是最简单的了，其次就是这个
$$K\space \space \space M\space \space \space P$$

但是实话实说KMP的难度就已经很高了！~~高到让我把拓展KMP（Z函数）剪了~~尤其是那个神秘的$kmp[maxn]$，它到底是怎样减小指针回跳的，为什么可以，很难懂。

不要慌，我们一起来解决这个神奇的算法。

首先。KMP是1对1的匹配，也就是说不能同时检测多个串在一个串中的出现位置。如果有$k$个串，那就要跑$k$遍，复杂度很高。

首先肯定是万能的暴力。这里建议自己实现以下BF算法：

```cpp
#include<bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    string t;
    cin>>s>>t;
	int slen=s.size();
	int tlen=t.size();
	int j=0;
    for(int i=0;i<slen;i++)
    {
        if(s[i]==t[j])
        {
            if(j==tlen-1)
            {
                cout<<i-tlen+1;
                return 0;
            }
            j++;
        }
        else
        {
            j=0;
        }
    }
	cout<<-1;
    return 0;
}
```

~~当然你可以压行（~~

我们发现这样做要扫完整个样本串，搞不好还要扫很多遍模式串，总体是个$O(n^2)$的复杂度。

这个算法还是太慢了，对于很多题目的$1e6$的数据规模无法承受。我们想想怎么优化，比如说搞点“优雅的暴力”什么的(bushi)

你别说还真的可以。

我们看上面的BF代码，如果$i$和$j$指向的字符不一致，那$j$就会直接掉回开头，如果$j$很长的话，这显然没必要，因为我们已经知道$j$前面的字符是能正确匹配的，为什么要为了一个字符，就撤掉整个集体的成果呢？这不好。我们考虑对模式串的每个位置建立一个“回跳表”，这个回跳表里的数值要尽可能大，省得我们一次跳太长。对于这个“回跳表”，我们直接开个数组$kmp$表示吧。

这里再做些约定：

- **我们的字符串从$1$开始编号**。KMP的实现有两种，**判未来法**对应的就是1开始，还有种**判当前位置的**是从0开始，1开始的代码虽较难理解，但一般更短，所以我们从1开始，但是BF代码是从0开始的，留意哦。

- 我们规定$kmp[i]$表示在字符串的$[1,i]$的字符所构成子串的**最长相同前缀后缀的长度**。

> 前缀指的是比原串而言，末尾少了若干个（不为0个）**连续**字符的子串，比如说`aling`的前缀有：`a`,`al`,`ali`,`alin`
>
> 后缀指的是比原串而言，开头少了若干个（不为0个）**连续**字符的子串，比如说`aling`的后缀有：`g`,`ng`,`ing`,`ling`
>
> 相同前后缀就是一个字符串的前后缀中相同的子串，**可能有多个**，如`aabaaaba`就有`a`和`aaba`两个相同前后缀，其中`aaba`是最长的。**并且作为前和后缀时也可以重叠**，如`aabaaba`的最长相同前后缀也是`aaba`。

为什么kmp数组要定义一个这么奇怪的量呢？我们先别管，~~反正证明从来都没给过~~，先用着（

还有，这里的kmp数组在其他文献里也可能命名为$next$，请注意联系。

我们先找个好字符串打表~~出省一~~玩玩。

$$
\begin{aligned}
A=“abaabaabbabaaabaabbabaab”\\
B=“abaabbabaab”
\end{aligned}
$$

你看看，匹配结果如下：

$$abaabaabbabaa\color{#52C41A}{abaabbabaab}$$

我们对模式串B打个kmp表（$j$指针指向它嘛,它回跳得远些嘛）。如下：

```plain text
str:a b a a b b a b a a b
kmp:0 0 1 1 2 0 1 2 3 4 5
```

不是回文串，不要算错了哦，这里我们定义$kmp[0]=0$，你可以自己先想想，后面我们再讲（逃）

接下来我们就从$i=1$开始匹配（$j$等于0），因为是预判未来，所以是`a[i]==b[j+1]`。不出意料的话，你可以一路匹配到$i=6,j=5$，也就是两个字符串的第6位（第一个字符为第1位）并不一致。

那我们查$kmp$，哦，$j=5$时，前2个字符是绝对匹配的。再一看，a[6]==b[3]，$good$。

那我们继续匹配。直到$i=14,j=11$，这个位置又不相等了，查$kmp[11]=5$，再一看，a[14]!=b[6]，那么没办法，$kmp[5]=2$，诶，a[14]==b[3]！好！

那我们继续匹配，直到$i=15,j=4$，查$kmp[4]=1$，a[15]==b[2]

那我们继续匹配，最终在$i=24,j=11$，没有任何差异，而b的范围确实是$[1,11]$，a的范围也是$[1,24]$。我们就判断出来了，b在a中确实存在，开头的索引呢？既然最后a[24]==b[11]可以判断字符串曾出现过，那肯定前面都是相等的。我们就直接输出i-b.len！……还要+1，你可以数数。

代码示例：

```cpp
for(int i=1;i<=alen;i++)//最坏走遍样本串
{
  while(j&&a[i]!=b[j+1])j=kmp[j];//j小于等于0会非法访问
  if(a[i]==b[j+1])j++;//如果等于就往前走
  if(j==blen-1)
  {
    cout<<i-blen+1;
    j=kmp[j]//如果要找到多个匹配索引，那么就回跳到最优的位置。
  }
}
```

好，这个问题就解决了！诶……还有个重要前提，我们怎么制作$kmp$数组呢？一个个数打表？不行吧，我们必须找个办法让程序自动把$kmp$数组做出来。

KMP的发明者们提出了一个巧妙的办法：用b匹配b自己，就像你先前对b匹配a做的那样。但是用原来的函数肯定是不行的（自身为什么不能完全匹配自己？），所以我们要做点小改动。

首先我们判断，$kmp[1]=0$是必然的。因为不能等于自身的情况下，单个字母的前后缀必然为空。所以我们的$i$循环直接从2开始。

我们模拟一下：

- kmp[2]:b[2]!=b[3],j=kmp[1]=0,查表，kmp[2]是0。

- kmp[3]:b[3]==b[1],j++,j=1,查表，kmp[3]=1。

- kmp[4]:b[4]!=b[2],j=kmp[2]=0,b[4]==b[1],j++,j=1,查表，kmp[4]=1。

- kmp[5]:b[5]==b[2],j++,j=2,查表，kmp[5]=2。

- kmp[6]:b[6]!=b[3],j=kmp[3]=1,b[6]!=b[1],j=kmp[1]=0,查表，kmp[6]=0

如此递推，你可以算出全部的kmp[i]。我们发现，按照匹配代码跑过一遍，最后$j$和kmp[i]有着相等的关系。为什么呢？

- 首先我们明白，对于第$i$轮循环，$j$的值其实是第$i-1$轮赋的，并且在数值上等于$kmp[i-1]$，而$kmp[i-1]$就是上一轮的答案。

- 根据定义，我们知道字符串中$[1,kmp[i-1]]$部分就是$[1,i-1]$部分的最大公共前后缀。

- 那么，我们判断`b[i]==b[j+1]`，就可以视为能不能第$i$个字符能不能“拼”在第$kmp[i-1]$个字符的后面。如果可以，我们就拼，并且更新到我们的$kmp[i]$中，为$kmp[i+1]$的计算做好准备。

- 如果不行，我们就尝试找到一个$kmp[k]$，使得`b[i]==b[kmp[k]+1]`，也就是一个能拼的子串的答案。

- 为什么能这样呢？我们回想到kmp数组的定义，$kmp[i]$指的是一个字符串$[1,i]$构成的子串的最长相等前后缀的长度，也就是说，$[1,kmp[i]]$和 $[kmp[i]+1,i]$这两部分只有三种可能：

1. 两部分完全匹配
 
  2. 后者是前者的子串
 
  3. 前者是后者的子串（后者可能比前者长）
 
  对于2，3两种情况，我们可以证明子串必然是纯后缀
 
  不管是哪一种情况，对于$[kmp[i]+1,i]$的字符，我们都可以在$[1,kmp[i]]$找到一个字符与其**对应**，那么对于第$i+1$个字符，我们分情况讨论。

就比如我们打串c=`abababa`的$kmp$数组。我们可以知道$kmp[5]=3$，易得$c[4,5]$是$c[1,3]$的后缀，这个时候我们要更新$kmp[6]$，我们就判断c[6]能不能在前5个字符中找到对应的字符。

- 这个$kmp[i]$的精髓就在于它可以这样**只由自身得到**，只跟自身有关，所以**只要你要查找的内容不变，不管是从什么文本里面查找，都不用重新打$kmp$数组**，这也是为什么进行1对多匹配时，我们只需要进行多次查询，而不用打多个$kmp$数组。

我们把代码写出来：

```cpp
kmp[1]=0;
int j=0;
for(int i=2;i<=blen;i++)
{
  while(j&&b[i]!=b[j+1])j=kmp[j];
  if(b[i]==b[j+1])j++;
  kmp[i]=j;
}
```

### 习题3.1.1

[P3375 【模板】KMP](https://www.luogu.com.cn/problem/P3375)

AC Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;

char a[maxn],b[maxn];
int kmp[maxn];

int main()
{
	cin>>a+1>>b+1;
	int alen=strlen(a+1),blen=strlen(b+1);
	int j=0;
	kmp[1]=0;
	for(int i=2;i<=blen;i++)
	{
		while(j>0&&b[i]!=b[j+1])j=kmp[j];
		if(b[i]==b[j+1])j++;
		kmp[i]=j;
	}
	j=0;
	for(int i=1;i<=alen;i++)
	{
		while(j>0&&a[i]!=b[j+1])j=kmp[j];
		if(a[i]==b[j+1])j++;
		if(j==blen)
		{
			cout<<i-blen+1<<endl;
			j=kmp[j];
		}
	}
	for(int i=1;i<=blen;i++)
	{
		cout<<kmp[i];
		if(i<blen)cout<<' ';
	}
	return 0;
}
```

### 习题3.1.2

[P4391 [BOI2009]Radio Transmission无线运输](https://www.luogu.com.cn/problem/P4391)

首先这个题是求最小周期串（虽然要求的是长度，但是你从$1$打印到答案位置不也是一个串嘛），它这个是一个串里求周期，收起你回文串DP的代码（

然后题目只给了一个串，但是我们还是可以想起KMP自身打$kmp$数组的代码。默默地偷看一眼哈。

然后我们看到了了不得的一行：

```cpp
if(b[i]==b[j+1])j++;
```

这个`==`就令人觉得KMP可行，为什么呢？求周期嘛，毕竟数学书里关于函数周期的定义就是：

$$f(x)=f(x+T),T\in \mathbb{R}$$

当然这个是$\mathbb{N^*}$，还是$\mathbb{C}$，那就看你选的什么了。

我们想到上面讲过的一段话：

> - 首先我们明白，对于第$i$轮循环，$j$的值其实是第$i-1$轮赋的，并且在数值上等于$kmp[i-1]$，而$kmp[i-1]$就是上一轮的答案。
>
> - 根据定义，我们知道字符串中$[1,kmp[i-1]]$部分就是$[1,i-1]$部分的最大公共前后缀。
?
> - 那么，我们判断`b[i]==b[j+1]`，就可以视为能不能第$i$个字符能不能“拼”在第$kmp[i-1]$个字符的后面。如果可以，我们就拼，并且更新到我们的$kmp[i]$中，为$kmp[i+1]$的计算做好准备。
>
> - 如果不行，我们就尝试找到一个$kmp[k]$，使得`b[i]==b[kmp[k]+1]`，也就是一个能拼的子串的答案。

也就是说，我们可以尝试找到最大相等前后缀和最小周期串之间的关系。

然后我们再想到上面的话：

> - 为什么能这样呢？我们回想到kmp数组的定义，$kmp[i]$指的是一个字符串$[1,i]$构成的子串的最长相等前后缀的长度，也就是说，$[1,kmp[i]]$和 $[kmp[i]+1,i]$这两部分只有三种可能：
>
>  1. 两部分完全匹配
> 
>  2. 后者是前者的子串
> 
>  3. 前者是后者的子串（后者可能比前者长）

对于第一种情况，我们就发现，如果两部分完全相等的话，那不恰好是两个周期吗？所以我们可以提出一个可能的规律：

最小周期串长度=字符串总长-最大相等前后缀长度

我们先把这个式子抽象成符号：

$$T=n-kmp[n]$$

现在的问题是，对于第二、三种情况这个式子成不成立呢？我们可以拿样例玩一下，毕竟样例就是第二种情况。显然式子是成立的，那就要给证明了（

首先题目中的字符串是有特殊性质的，字符串的长度一定大于等于$2$个周期。那么，我们肯定可以通过切片，把最小周期串切出来。而且切得好的话还能切出两个。

AC Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;

char a[maxn];
int kmp[maxn];
int len=0;

int main()
{
	cin>>len>>a+1;
	int j=0;
	kmp[1]=0;
	for(int i=2;i<=len;i++)
	{
		while(j>0&&a[i]!=a[j+1])j=kmp[j];
		if(a[i]==a[j+1])j++;
		kmp[i]=j;
	}
	cout<<len-kmp[len];
	return 0;
}
```

### 习题3.1.3

[P3435 [POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435)

AC Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+7;

char a[maxn];
int len=0;
int kmp[maxn];
long long res=0;

int main()
{
	cin>>len;
	cin>>a+1;
	int j=0;
	kmp[1]=0;
	for(int i=2;i<=len;i++)
	{
		while(j>0&&a[i]!=a[j+1])j=kmp[j];
		if(a[i]==a[j+1])j++;
		kmp[i]=j;
	}
	for(int i=2,j=2;i<=len;i++,j=i)
	{
		while(kmp[j]>0)j=kmp[j];
		if(kmp[i]>0)kmp[i]=j;
		res+=i-j;
	}
	cout<<res;
	return 0;
}
```

# 4.AC自动机

提到这个，就不得不想起当时搞工程，学编译原理，然后在词法分析阶段乱画自己设定的语言的DFA（确定状态有穷自动机，与本文无关）。当时觉得这个东西到底是个啥，根本不会，现在发现基本上就是个AC自动机。只是有一点点小区别。

那个想研发的语言早就删库跑路了……（

AC自动机，就是前面提到的**一对多**匹配，主要是解决一个样本串中给定的多个字符串出现了多少次、出现位置的索引之类的问题。

我们的一个想法就是直接建棵$trie$，然后把多个字符串都插进来，最后用样本串查询！查询一个成功后就跳回根节点，然后索引往后挪一位（相当于把前面的删掉），然后再查询，就可以了！

但是这样的复杂度显然很高！事实上，如果成功了还好，失败了就完蛋了，因为每次失败都要跳回根节点重新查找，效率自然就低了（

那这个时候，我们就需要KMP的思想，尽可能的少回跳字符。

### 习题4.1.1

[P3808 AC自动机（简单版）](https://www.luogu.com.cn/problem/P3808)

AC Code：

```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+7;

int getnum(char x)
{
	return x-'a';
}
int id=0;

struct trie
{
	int children[maxn][26];
	int cnt[maxn];
	
	void insert(string s);
};
trie ACM;

void trie::insert(string s)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		int letter=getnum(s[i]);
		if(children[p][letter]==0)children[p][letter]=++id;
		p=children[p][letter];
	}
	cnt[p]++;
}

int fail[maxn];
int vis[maxn];

void build()//建ACM
{
	queue<int> q;
	for(int i=0;i<26;i++)
	{
		if(ACM.children[0][i])q.push(ACM.children[0][i]);
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int v=ACM.children[u][i];
			if(v)
			{
				fail[v]=ACM.children[fail[u]][i];
				q.push(v);
			}
			else ACM.children[u][i]=ACM.children[fail[u]][i];
		}
	}
}

int query(string s)
{
	int ans=0;
	for(int i=0,k=0;k<s.size();k++)
	{
		i=ACM.children[i][getnum(s[k])];
		for(int j=i;j&&!vis[j];j=fail[j])
		{
			ans+=ACM.cnt[j];
			vis[j]=1;
		}
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string s;
	string t;
	int n=0,res=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		ACM.insert(s);
	}
	build();
	cin>>t;
	res=query(t);
	cout<<res;
	return 0;
}
```