重生之我与字符串的殊死搏斗

wangzilong913: 该死的字符串，纳命来！！

string: 就凭你？吃我一招最小表示法橫劈！！

一.最小表示法

1.基本概念：

给定一个字符串，如果我们不断把它的最后一个字符放到开头，最终得到

n

个字符串，我们称这

n

个字符串是循环重构的。这些字符串中字典序最小的一个，称为字符串

S

的最小表示。

（字典序：在比较字典序中，首先比较两个字符串的第一个字符，如果不同，则第一个字符较小的字符串更小；如果相同，则继续比较下一个字符，依此类推，直到比较完所有字符。如果一个字符串是另一个字符串的前缀，则较短的字符串更小。）

2.基本原理：

首先把

S

复制一份接在它的结尾，得到字符串

SS

。显然，以

i

开始的循环同构字符串

B[i

i+n-1] = SS[i

i+n-1

。

如果在

i+k

与

j+k

处发现不相等，假设

SS[i+k] > SS[j+k]

，那么我们当然可以得知

B[i]

不是

S

的最小表示（因为存在一个更小的循环同构串

B[j]

）。除此之外，我们还可以得知

B[i+1],B[i+2]......,B[i+k]

也都不是

S

的最小表示。这是因为对于

1<=p<=k

，存在一个比

B[i+p]

更小的循环同构串

B[j+p]

（从

i+p

与

j+p

开始扫描，同样会在

p=k

时发现不相等，并且

SS[j+p]>SS[j+k]

）。

同理，如果

SS[i+k]<SS[j+k]

，那么

B[j+1],B[j+2]......,B[j+k]

都不是

S

的最小表示，直接跳过这些位置，一定不会遗漏最小表示。

因此，我们可以做到用

O(n)

的时间复杂度求出字符串的最小表示。

3.模板：

P1368 【模板】最小表示法

注：原题是整数的最小表示，此处写的是字符串

CPP

#include <bits/stdc++.h>
using namespace std;
int n,ans;
char a[6000010];
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		a[i+n] = a[i];
	}
	int i = 1,j = 2,k;
	while(i <= n && j <= n){
		for(k = 0;k < n && a[i+k] == a[j+k];k++);
		if(k == n) break;
		if(a[i+k] > a[j+k]){
			i = i + k + 1;
			if(i == j) i++;
		}
		else{
			j = j + k + 1;
			if(i == j) j++;
		}
	}
	ans = min(i,j);
	for(int i = ans;i < ans+n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

string: 居然抗住了这一刀，看来是小瞧你了。

wangzilong: 代码量又小，理解也不难，你看这string就是逊啊！！

string: 哟，这么说你很勇咯。区区蝼蚁，也妄想挑战我。看我这招Trie树诛仙锁！！

二.Trie树

1.基本概念：

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。

Trie树的基本性质：

根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。

2.实现

插入：

当需要插入一个字符串

S

时，我们令一个指针

P

起初指向根节点。然后依次扫描

S

中的每一个字符

c

。

若 $P$ 的 $c$ 字符指向一个已经存在的节点 $Q$ ，则令 $P=Q$ 。
若 $P$ 的 $c$ 字符指向空，则新建一个节点 $Q$ ，令 $P$ 的 $c$ 字符指针指向 $Q$ ，然后令 $P=Q$ 。

当

S

中的字符扫描完毕时，在当前节点

P

上标记它是一个字符串的末尾。

检索：

当需要检索一个字符串

S

在Trie树中是否存在时，我们令一个指针

P

起初指向根结点，然后依次扫描

S

中的每个字符

c

：

若 $P$ 的 $c$ 字符指向空，则说明 $S$ 没有被插入过Trie树，结束检索。
若 $P$ 的 $c$ 字符指向一个已经存在的节点 $Q$ ，则令 $P=Q$ 。

当

S

中的字符扫描完毕时，若当前节点

P

被标记为一个字符串的末尾，则说明

S

在Trie树中存在，否则说明

S

没有被插入过Trie树。

3.模板：

P10470 前缀统计

CPP

#include <bits/stdc++.h>
using namespace std;
int n,m;
int t[1000005][26];
int cnt[1000005];
int now;
void cha(string s){
	int p=0;
	for(int i = 0;i < (int)s.size();i++){
		if(t[p][s[i]-'a'] == 0){
			t[p][s[i]-'a'] = ++ now;
		}
		p = t[p][s[i]-'a'];
	}
	cnt[p]++;
}
int zhao(string s){
	int p=0,m=0;
	for(int i = 0;i < (int)s.size();i++){
		if(t[p][s[i]-'a'] == 0){
			return m;
		}
		p = t[p][s[i]-'a'];
		m+=cnt[p];
	}
	return m;
}
int main(){
	cin>>n>>m;
	while(n--){
		string s;
		cin>>s;
		cha(s);
	}	
	while(m--){
		string s;
		cin>>s;
		cout<<zhao(s)<<endl;
	}
	return 0;
}

2024.12.21

文章操作

重生之我与字符串的殊死搏斗

一.最小表示法

1.基本概念：

2.基本原理：

3.模板：

二.Trie树

1.基本概念：

2.实现

插入：

检索：

3.模板：

相关推荐

评论

2024.12.21