【算法】零基础KMP、Trie、AC自动机

• • KMP
  • • 前后缀是什么
  • KMP题
  • • AcWing 831. KMP字符串
  • Trie
  • • AcWing 835. Trie字符串统计
  • AC自动机

字符串匹配的KMP算法–前缀和后缀的详解——看这个可以理解KMP
字符串匹配的KMP算法–前缀和后缀的详解——可以看到图的版本
AcWing 831. KMP字符串-KMP的个人理解和解析

假如有一个串：abaab(下标从1开始)
前缀：
a
ab
aba
abaa

后缀：（从后往前）
b
ab
aab
baab

“部分匹配值”：前缀和后缀的最长共有元素的长度。

所以这个串的部分匹配值是2，即next[5]=2.（5代表串的长度，即串的下标1-5）

next[i]=j的含义是：
模板串p中，p[1,j]=p[j-j+1,i];

如上面的串：abaab中next[5]=2.
即，串[1,2]=串[4,5]=ab

关于怎么匹配，看AcWing 831. KMP字符串-KMP的个人理解和解析的三、匹配思路和实现代码部分：

AcWing 831. KMP字符串

哎，理解了但没完全理解，基本对着视频打的，希望能通过做题慢慢学会吧。

#include
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e5+10,M=1e6+10;
char p[N],s[M];//p是模板串 是短一点的那个 
int n,m;
int ne[N];
int main()
{
	cin>>n>>p+1;
	cin>>m>>s+1;//字符数组从1开始读入 
	
	//求next数组 i从2开始，因为next[1]=0 退无可退了 
	for(int i=2,j=0;i<=n;i++) 
	{
		while(j&&p[i]!=p[j+1]) j=ne[j];//j还能退 且没匹配到（就要退）
		
		if(p[i]==p[j+1]) j++;//匹配到了 继续往下匹配
		 
		ne[i]=j;
	}
	
	//KMP 匹配
	for(int i=1,j=0;i<=m;i++) 
	{
		while(j&&s[i]!=p[j+1]) j=ne[j];
		
		if(s[i]==p[j+1]) j++;
		
		if(j==n) //匹配成功
		{
			cout< 
Trie 
AcWing 835. 如何理解单(双)链表，Trie树和堆中的idx？
 AcWing 835. Trie字符串统计
 
Trie树：高效地存储和查找字符串集合的数据结构。
 一般会用Trie树的题，它的集合中，要么都是小写字母、或大写字母、或数字、或01——种类的数量不会太多。
 
有一个字符串集合：
 
 这个字符串集合的Trie树是：
 
 从根节点到星号的每一个字母的集合就是字符串集合中的其中一个字符串。
 （用星号标记字符串到这里已经结束了）
 
AcWing 835. Trie字符串统计 
AcWing 835. Trie字符串统计
 
#include
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e5+10;

int son[N][26],cnt[N],idx;


char str[N];

void insert(char *str)//传入一个字符数组 
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int u=str[i]-'a';
		if(!son[p][u]) //没有这个节点 
			son[p][u]=++idx;//创建一个节点 编号是idx
		p=son[p][u]; 
	}
	cnt[p]++;//结束时的标记，记录以此节点结束的字符串个数 
}

int query(char *str)
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int u=str[i]-'a';
		if(!son[p][u]) return 0;//没有这个节点
		p=son[p][u];//一直找它的结尾 
	}
	return cnt[p];
}
int main()
{
	int t;cin>>t;
	while(t--)
	{
		char ch;
		cin>>ch>>str;
		if(ch=='I') insert(str);		
		else cout< 
AC自动机