专栏文章

学习笔记-字符串

YYGBC_
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzreaq
此快照首次捕获于
2025/12/01 18:13
3 个月前
此快照最后确认于
2025/12/01 18:13
3 个月前
查看原文

字符串

算是一种数据结构，但知识点和用途较广泛，所以单开一节。

字符串哈希

通常使用字符串哈希实现两字符串之间快速比较。

进制哈希（BKDR Hash\text{BKDR Hash}）

将字符串当作 nn 进制数，然后进行计算（自然溢出）。
模板代码实现。
CPP
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
constexpr int X=1e4+5;
constexpr ull st=13131ull;

ull N,res,H[X];
string s[X];

ull make_hash(string &s)
{
	ull h=0;
	for(auto c:s)
		h*=st, h+=c;
	return h;
}

int main()
{
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>s[i];
		H[i]=make_hash(s[i]);
	}
	sort(H+1,H+N+1);
	for(int i=1;i<=N;i++)
		if(H[i]!=H[i-1]) res++;
	cout<<res;
	return 0;
}

STL 实现

利用 unordered_map 或 unordered_set 可以方便地实现字符串哈希。
如果怕被卡，可以使用 map 或者 set，复杂度要劣一些。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=1e4+5;

int N;
string s[X];
unordered_set<string> S;

int main()
{
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>s[i];
		S.insert(s[i]);
	}
	cout<<S.size();
	return 0;
}
大数据下可能会 MLE，也可以手压成 Hash 值然后装入 STL 容器。

字典树（Trie）

相当实用的数据结构，可以在串长复杂度内求解前缀匹配问题。可用于 AC 自动机的失配回溯。其变种 0-1 Trie 广泛用于求解异或问题。缺点是空间复杂度较劣。
核心是插入和查找。
插入时顺着节点编号向下记录，若遇到空节点就新增节点，查找类似。
模板代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=3e6+5;

int T,N,q;
string s;

struct Trie{
	struct Node{
		int p[128];
		int cnt;
		void clear()
		{
			for(int i=1;i<127;i++) p[i]=0; cnt=0;
		} 
	}t[X];
	int lst;
	void clear()
	{
		for(int i=0;i<=lst;i++) t[i].clear(); lst=0;
	}
	void insert(string &s)
	{
		int pos=0;
		for(auto c:s){
			if(!t[pos].p[c]) t[pos].p[c]=++lst;
			pos=t[pos].p[c];
			t[pos].cnt++;
		}
	}
	int query(string &s)
	{
		int pos=0;
		for(auto c:s){
			if(!t[pos].p[c]) return 0;
			pos=t[pos].p[c];
		}
		return t[pos].cnt;
	}
}Tr;

void solve()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); 
	Tr.clear();
	cin>>N>>q;
	while(N--){
		cin>>s;
		Tr.insert(s);
	}
	while(q--){
		cin>>s;
		cout<<Tr.query(s)<<'\n';
	}
}

int main()
{
	cin>>T;
	while(T--) solve();
}

KMP\text{KMP}

非常精妙，简洁，优秀的一个算法，用于在 O(n+m)O(n+m) 复杂度内求解字符串单模匹配问题，其使用 failfail 数组维护模式串的最长公共前后缀，以在失配后避免重新匹配。
代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=1e6+5;

int N,M,fail[X];
string s,p;

void print(int i)
{
	cout<<i-M+2<<'\n';
}

void get_fail()
{
	fail[0]=0, fail[1]=0;
	for(int i=1;i<M;i++){
		int j=fail[i];
		while(j&&p[i]!=p[j]) j=fail[j];
		if(p[i]==p[j]) fail[i+1]=j+1;
		else fail[i+1]=0;
	}
}

void KMP()
{
	int j=0;
	for(int i=0;i<N;i++){
		while(j&&s[i]!=p[j]) j=fail[j];
		if(s[i]==p[j]) j++;
		if(j==M){
			print(i);
			j=fail[j];
		} 
	}
}

int main()
{
	cin>>s>>p;
	N=s.size(), M=p.size();
	get_fail(); KMP(); 
	for(int i=1;i<=M;i++) cout<<fail[i]<<' ';
}

Manacher\text{Manacher}

一个能在 O(n)O(n) 复杂度内求解字符串中以各个字符为中心的最长回文串的半径长度。其核心是利用 ”回文在回文中的镜像也是回文“ 来避免暴力匹配。
下面是模板代码：
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int X=2.3e7;

int N,P[X],res;
string a,s;

void change()
{
	N=a.size();
	s.append("$#");
	for(int i=0;i<N;i++){
		s.push_back(a[i]);
		s.push_back('#');
	}
	s.push_back('&');
	N=s.size();
}

void Manacher()
{
	int R=0,C=0;
	for(int i=1;i<N;i++){
		P[i]=(i<R)? min(P[(C<<1)-i],P[C]+C-i):1;
		while(s[i+P[i]]==s[i-P[i]]) P[i]++;
		if(P[i]+i>R) R=P[i]+i,C=i;
		res=max(res,P[i]-1);
	}	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>a;
	change();
	Manacher();
    cout<<res; 
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...