最基础部分

定义

字符集，字符串（这东西显然不需要打一遍定义）

子串，这个东西表示一段连续的 $S[i...j],i\leq j$

有时候，用 $S[i...j],i>j$ 表示空串

子序列， $s[p_1...p_k],p_i$ 递增并且满足 $1\leq p_1<p_k\leq|S|$

前缀，从串首开始到某个位置的子串。

后缀，从某个位置到串末尾的子串。~~为啥每次都会打成猴嘴~~

字典序，顾名思义就是按照字符顺序比较的方法，或者说以第 $i$ 个字符为第 $i$ 关键字进行大小比较，空集是最小的

回文串，倒着和正着都一样的串

输入，输出

哈希

把一个子串映射成为一个数字，一般的写法是这样的

$f(S)=\sum s_ip^{|S|-i}$

我们先令 $n=|S|$ 那

$f(S)=s_1*p^{n-1}+s_2*p^{n-2}+...+s_n$

单独这样取模最后的结果太大了，我们还得模一个数，最好是质数，因为这样每个结果出现的概率相等（证明很容易，因此不放）。

代码写出来就是这样的

1	for(i=1;i<=n;i++) f[i]=(f[i-1]*p+s[i]-'a')%modp;

然而现在我们只有 $[1..i]$ 的哈希值，我们想要 $[l,r]$ 的哈希值，那怎么办呢？

首先我们找到 $l-1$ 的表达

$f(S[1..(l-1)])=s_1 \times p^{l-2}+s_2 \times p^{l-3}+...+s_{l-1}$

然后 $r$ 的表达

$f(S[1..(r)])=s_1\ times p^{r-1}+s_2 \times p^{r-2}+...+s_{r}$

观察第一项次数之差 $r-1-(l-2)= r+l+1$

那么我们给 $l-1$ 的表达乘 $p$ 的这么多次方即可

$f(S[1..(r)])-p^{r+l-1}\times f(S[1..(l-1)])$

即为所求(显然记过是要让你自己推以下的)

那么这东西有什么用呢？

如果两个字符串相等的话，那么他们的哈希值一定相等，但是并不能保证哈希值相等，这两个串相等，不过这种概率很小，而且不可避免，不过都写了哈希了基本都确定是在水分了，被卡一两个点也能接受。

哈希冲突的概率到底是多少？

我们取 $n$ 个哈希，每次都会有 $\frac{1}{modp}$ 的概率炸掉，那么炸掉的总概率是 $1-(1-\frac{1}{modp})^n$

但是这样算其实是有问题的，参考生日悖论也就是说冲突的概率大概是 $O(\sqrt{modp})$ 级别的，那怎么办呢？双哈希即可

Trie

#include<bits/stdc++.h>

using namespace std;

const int maxn=10086;

char a[120];

int t[maxn*26][26];
int eof[maxn*26],T,tot=1;

void ins_trie_tree(int x,int len,int mxlen)
{
//	cout<<a[len]<<endl; 
	if(len==mxlen+1)
	{
		eof[x]++;
		return ;
	}
	if(t[x][a[len]-'a']) ins_trie_tree(t[x][a[len]-'a'],len+1,mxlen);
	else t[x][a[len]-'a']=++tot,ins_trie_tree(tot,len+1,mxlen);
}

char tmp[120];

void coutree(int x,int dep)
{
	for(int i=1;i<=eof[x];i++)
	{
		printf("%s\n",&tmp[1]);
	}
	for(int i=0;i<=25;i++)
	{
		if(t[x][i])
		{
			tmp[dep+1]='a'+i;
			coutree(t[x][i],dep+1);
			tmp[dep+1]=0;
		}
	}
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",a+1);
		ins_trie_tree(1,1,strlen(a+1));
	}
	coutree(1,0);
}

低科技

KMP

~~这东西打这个发现是真的没懂，于是重新去学了一遍~~

我们考虑一般的字符串匹配问题，如果我们用哈希的话，运气好出题人是卡不掉的，但是出题人卡不卡的掉你全靠运气，所以有更保险的写法还是写更保险的吧（除非写不出来了）

我们定义 $\pi_i$ (实际上这东西也被人称为 $next$ 数组 )表示长度最大的前缀后缀长度使得前缀后缀相等,对于这个字符串，我们可以轻易地手推出 $\pi_i$

下标	1	2	3	4	5	6	7
$S$	a	b	c	a	b	c	d
$\pi$	$0$	$0$	$0$	$1$	$2$	$3$	$0$

这东西有什么用呢？我们先不考虑，来看看怎么求到这个数组

首先一个显然的办法是对每个位置暴力枚举前缀后缀，然后暴力比较，时间复杂度为 $O(n^3)$ ,优化可以用哈希，但是也应该注意到每次 $\pi_i \leq \pi_{i-1}+1$ 那么我们不用每一次都来重新枚举下标，实际上这个移动的上界也是很显然可以确定是 $O(N)$ 级别了，似乎我们已经优化成了 $O(N)$ 不过我们使用了哈希，我们继续推一下它的性质。

我们发现，因为最长移动距离是 $1$ 时，这时候必然有 $S_{\pi[i]+1}=s[i+1]$ 这时候 $\pi [i+1]=\pi[i]+1$ ,否则我们就在找到下一个更短的 $\pi_j$ 来贪心地匹配，想一下我们刚才得到的结论，发现预处理这个数组时间复杂度变成了 $O(N)$

，然后这样一来，我们之后匹配一个字符串来，有了 $\pi_i$ 我们就可以保证当前匹配出的长度只增不减，同时我们在原来的模式串跳，最坏的复杂度为依然为 $O(N)$

补一个代码

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1e6+10;

char ms[maxn],ts[maxn];
int pi[maxn];
int n,m;

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	scanf("%s %s",ts+1,ms+1);
	j=0;
	n=strlen(ms+1);
	for(i=2;i<=n;i++)
	{
		while(j&&ms[j+1]!=ms[i]) j=pi[j];
		if(ms[j+1]==ms[i]) j++;pi[i]=j;
	}
	m=strlen(ts+1);
	j=0;
	for(i=1;i<=m;i++)
	{
		while(j&&ms[j+1]!=ts[i]) j=pi[j];
		if(ms[j+1]==ts[i]) j++;
		if(j==n) cout<<i-n+1<<endl,j=pi[j];
	}
	for(i=1;i<=n;i++) cout<<pi[i]<<" ";
	return 0;
}