Hash & String 学习笔记

目录

        咕咕咕

Trie 树/字典树

       P8306 【模板】字典树

           咕咕咕（感觉比较简单（吗））（我才不会说是我懒呢）

KMP

        一个求最长公共前后缀的东西

        P3375 【模板】KMP

        写法一

#include<bits/stdc++.h>
using namespace std;
int nxt[2000005];
string s1,s2;
void get_nxt(string b)
{
	for(int k=1,l=0;k<b.length();k++)
	{
		while(b[k]!=b[l] && l>0) l=nxt[l-1];
		if(b[k]==b[l]) l++;
		nxt[k]=l;
	}
}
//求最长公共前后缀
void kmp(string a,string b)
{
	for(int k=0,l=0;k<a.length();k++)
	{
		while(a[k]!=b[l] && l>0) l=nxt[l-1];
		if(a[k]==b[l]) l++;
		if(l==b.length()) cout<<k+2-b.length()<<"\n";
	}
}
//匹配
int main()
{
	cin>>s1>>s2; get_nxt(s2); kmp(s1,s2);
	for(int i=0;i<s2.length();i++) cout<<nxt[i]<<' ';
	return 0;
}

        写法二（从大佬那学来的~）

直接把s2接在s1后面
匹配的公共前后缀中长度等于le2的时候，满足条件
然后会发现，get_nxt求的是最长的，
于是往前跳，并进行路径压缩
时间复杂度均摊O(1)  (吗)

#include<bits/stdc++.h>
using namespace std;
int l2,nxt[2000005],fl[2000005];
string s1,s2;
int get(int x)
{
	if(fl[x]) return fl[x];
	if(x<l2) { fl[x]=2; return 2; }
	return fl[x]=get(nxt[x-1]);
}
void kmp(string b)
{
	for(int k=1,l=0;k<b.length();k++)
	{
		while(b[k]!=b[l] && l>0) l=nxt[l-1];
		if(b[k]==b[l]) l++;
		nxt[k]=l;
	}
}
int main()
{
	cin>>s1>>s2; l2=s2.length(); fl[l2]=1;
	s1=s2+s1; kmp(s1);
	for(int i=l2+l2-1;i<s1.length();i++) if(get(nxt[i])==1) cout<<i-l2-l2+2<<"\n";
	for(int i=0;i<l2;i++) cout<<nxt[i]<<" ";
	return 0;
}

manacher/马拉车

        没想到，马拉车居然是直接音译的     

        这是一个关于回文串的O（n）算法

P3805 【模板】manacher

写法一

        用d[i]表示以i为中间为的回文串单侧的长度

//oiwiki上的描述更加清晰

#include<bits/stdc++.h>
using namespace std;
int l,r,le,k,d[110000005],ma;
string s;
int main()
{
	cin>>s; le=s.length();
	l=0,r=-1;//l 和 r 分别为该回文串左右边界的位置
	for(int i=0;i<le;i++)
	{
		k=(i>r)?1:min(r-i+1,d[l+r-i]);
        //若当前位置不在当前段内，暴力枚举
		while(i+k<le && i-k>=0 && s[i+k]==s[i-k]) k++;
		d[i]=k--; ma=max(ma,k*2+1);
		if(i+k>r) r=i+k,l=i-k;
	}
    //先做长度为奇数的，即中间位为i
	memset(d,0,sizeof d); l=0,r=-1;
	for(int i=0;i<le;i++)
	{
		k=(i>r)?0:min(r-i+1,d[l+r-i+1]);
		while(i+k<le && i-k-1>=0 && s[i+k]==s[i-k-1]) k++;
		d[i]=k--; ma=max(ma,(k+1)*2);
		if(i+k>r) r=i+k,l=i-k-1;
	}
    //做长度为奇数的  注意细节
	cout<<ma;
	return 0;
}

写法二

#include<bits/stdc++.h>
using namespace std;
int le,l,r,k,ma,d[22000005];
string s,ss;
int main()
{
	cin>>s; le=s.length();
	ss+='^'; ss+='#'; r=-1;
//在串中各一位加入一个原本没有的字符
//在头和尾加入字符，可以不用判边界，还可以防止越界
	for(int i=0;i<le;i++) ss+=s[i],ss+='#'; ss+='@';
//在加入后，对奇串不影响，会事原本的偶串变为以#为中间位置的奇串
//然后就安神找奇串做一遍
	le=le*2+1;
	for(int i=1;i<=le;i++)
	{
		k=(i>r)?1:min(r-i,d[l+r-i]);
		while(ss[i-k]==ss[i+k]) k++;
		d[i]=k--; ma=max(ma,(i&1)?(k+1)/2*2:1+k/2*2);
//这里求最大值可能有点抽象，不过由于太菜了，还没想到什么别的算法
//有的话可以私信
		if(i+k>r) l=i-k,r=i+k;
	}
	cout<<ma;
	return 0;
}