字符串

AisDaeun 19 2023-10-29

Hash

Hash是一种字符串到数字的映射,通过映射后可以O(1)地检测两个子串是否相等。

Hash函数有很多,一般比较常用的是进制Hash。它有许多优点,如重复率低、可以简单地求出字符串对应子串的Hash映射。

由于对所有字符串映射到不同的数字上所需的数集太大,实际应用中一般对结果取余。不过,这样就存在出错的可能。

算法竞赛中,为了防止特意构造的数据使Hash出错,一般使用双哈希,一个模数是大质数,另一个模数可以使用unsigned long long自动溢出,相当于对2^{64} - 1取模。

进制一般使用13131、131313这些数,映射较均匀。

P3370 【模板】字符串哈希

#include <bits/stdc++.h>
using ll = long long;
const ll N = 1510, P = 131313, M = 1e9 + 7;
char str[N];
ll get(char *s) {
	ll ans {0};
	while (*s) ans = (ans * P + *s++) % M;
	return ans;
}
std::set<ll> s;
signed main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", str);
		s.emplace(get(str));
	}
	printf("%llu\n", s.size());
}

Manacher

manacher是一种线性时间求解回文串数量的算法。

P3805 【模板】manacher

#include <bits/stdc++.h>
#define int long long
#define min(a, b) (a) < (b) ? (a) : (b)
#define max(a, b) (a) > (b) ? (a) : (b)
const int N = 2.2e7 + 10;
char s[N];
int p[N], n, ans;
void input() {
	char ch = getchar();
	while (!isalpha(ch)) ch = getchar();
	s[0] = '&', s[++n] = '#';
	while (isalpha(ch)) {
		s[++n] = ch;
		s[++n] = '#';
		ch = getchar();
	}
	s[++n] = '$';
}
void manacher() {
	int r = 0, c;
	for (int i = 1; i < n; i++) {
		if (i < r) p[i] = min(p[c * 2 - i], p[c] + c - i);
		else p[i] = 1;
		while (s[i + p[i]] == s[i - p[i]]) p[i]++;
		if (p[i] + i > r) {
			r = p[i] + i;
			c = i;
		} 
	}
}
signed main() {
	input();
	manacher();
	for (int i = 0; i < n; i++) ans = max(ans, p[i]);
	printf("%lld\n", ans - 1);
}

Trie

Trie是一种高效查询多个字符串的数据结构,其缺点是占用空间较大。

具体来说,可以看做将字符串按位分解,每一位看作树中的一个节点。每个节点向字符串下一位对应的节点连一条边。

实现时,方便起见,一般设每个节点和字符集连一条边,如果这条边不合法,则将其连向根节点。根节点也是一个虚点,没有实际意义,一般设它的编号为0。

模板题:P8306 【模板】字典树

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int Map[256];
int trie[N][62], cnt[N], idx;
char str[N];
int n, q;
void insert(char *s) {
	int p = 0;
	for (int i = 0; s[i]; i++) {
		int j = Map[(int)s[i]];
		if (trie[p][j] == 0)
			trie[p][j] = ++idx;
		p = trie[p][j];
		cnt[p]++;
	}
}
int search(char *s) {
	int p = 0;
	for (int i = 0; s[i]; i++) {
		int j = Map[(int)s[i]];
		if (trie[p][j] == 0) return 0;
		p = trie[p][j];
	}
	return cnt[p];
}
int main() {
	for (int i = 0; i < 10; i++)
		Map[i + '0'] = i;
	for (int i = 0; i < 26; i++)
		Map[i + 'a'] = 10 + i;
	for (int i = 0; i < 26; i++)
		Map[i + 'A'] = 10 + 26 + i;
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &q);
		for (int i = 0; i <= idx; i++) {
			for (int j = 0; j < 62; j++)
				trie[i][j] = 0;
			cnt[i] = 0;
		}
		idx = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%s", str);
			insert(str);
		} 
		for (int i = 1; i <= q; i++) {
			scanf("%s", str);
			printf("%d\n", search(str));
		}
	}
}

KMP

KMP是一种线性时间求解模式匹配的算法。

模板题:P3375 【模板】KMP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char pat[N], txt[N];
int fail[N], n, m;
void getFail() {
	for (int i = 2, j = 0; i <= n; i++) {
		while (j > 0 && pat[i] != pat[j + 1]) j = fail[j];
		if (pat[i] == pat[j + 1]) j++;
		fail[i] = j;
	}
}
void calc() {
	for (int i = 1, j = 0; i <= m; i++) {
		while (j > 0 && (j == n || txt[i] != pat[j + 1])) j = fail[j];
		if (txt[i] == pat[j + 1]) j++;
		if (j == n) printf("%d\n", i - n + 1);
	}
}
int main() {
	scanf("%s%s", txt + 1, pat + 1);
	n = strlen(pat + 1), m = strlen(txt + 1);
	getFail();
	calc();
	for (int i = 1; i <= n; i++) printf("%d ", fail[i]);
}