首页

# 哈希

# 字符串哈希

把一个字符串转换成一个数，用于判断相同或者用于匹配什么的。

常用转化成 base 进制数，随便取进制数 base 和模数 mod 搞一搞什么的。

P3370 【模板】字符串哈希

题意：给出一堆字符串 (1e5 个，长度 1500)，问有多少不同的字符串。

会被卡掉的单模：

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int MAXN = 1e5 + 233, base = 233, mod = 19260817;
int n;
char str[2333];
vector<int> val;
int getHash()
{
	int len = strlen(str), ans = 0;
	rep (i, 0, len - 1)
		ans = (ans * base % mod + str[i])% mod;
	return ans;
}
int main()
{
	scanf("%d ", &n);
	rep (i, 1, n)
	{
		gets(str);
		val.push_back(getHash());
	}
	sort(val.begin(), val.end());
	printf("%d\n", unique(val.begin(), val.end()) - val.begin());
	return 0;
}

双模（某位 z 姓长者说双模很稳）：

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int MAXN = 1e5 + 233, base = 233, mod = 19260817, mod2 = 10000019;
int n;
char str[2333];
vector<pair<int, int> > val;
pair<int, int> getHash()
{
	int len = strlen(str);
	pair<int, int> ans{0, 0};
	rep (i, 0, len - 1)
	{
		ans.first = (ans.first * base % mod + str[i])% mod;
		ans.second = (ans.second * base % mod2 + str[i])% mod2;
	}
	return ans;
}
int main()
{
	scanf("%d ", &n);
	rep (i, 1, n)
	{
		gets(str);
		val.push_back(getHash());
	}
	sort(val.begin(), val.end());
	printf("%d\n", unique(val.begin(), val.end()) - val.begin());
	return 0;
}

# 字典树 Trie

一棵树，（除了根）每个节点上有字母，每条（从根开始的）链对应一个字符串。

操作：

  • 初始化：根节点置为空。
  • 插入：扫描待插入串的每一个字符，沿着走，不存在的点创建一下。在末尾处标记节点。
  • 查询：扫描待查询串的每一个字符，沿着走。能走到末尾 且 在此处有标记 则该串存在，否则不存在。

P3370 【模板】字符串哈希

题意：给出一堆字符串 (1e5 个，长度 1500)，问有多少不同的字符串。

唔.. 按这个数据范围大概需要 1e5*1500​ 个节点。。？指针是不可能的，这辈子都不可能的

70pts 数组写法：

#include <cstdio>
#include <iostream>
#include <cstring>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int MAXN = 2e5 + 233;
int n, ans, tmp;
char str[2333];
int trie[MAXN][60]; //[0-9a-zA-Z]
bool vis[MAXN]; //end of a string
int getId(char ch)
{
	if ('0' <= ch && ch <= '9')
		return ch - '0';
	if ('a' <= ch && ch <= 'z')
		return ch - 'a' + 10;
	return ch - 'A' + 36;
}
void add()
{
	int len = strlen(str);
	int np = 0; //root
	rep (i, 0, len - 1)
	{
		int id = getId(str[i]);
		if (!trie[np][id])
			trie[np][id] = ++tmp;
		np = trie[np][id];
	}
	if (!vis[np])
		ans++;
	vis[np] = 1;
}
int main()
{
	scanf("%d ", &n);
	rep (i, 1, n)
	{
		gets(str);
		add();
	}
	printf("%d\n", ans);
	return 0;
}

# KMP 字符串匹配

给出文本串 a (一般较长) ，模式串 b (一般较短)，问 b 在 a 中出现的位置。

留给自己：别再拿着模式串左右横跳了，串站着别动，指针动。。

匹配方式：

  • 两个指针， i 指向文本串， j 指向模式串， 每次判断 a[i]a[i] 与 b[j+1]b[j + 1] 是否相等。
  • 相等则继续，不相等的话，j 回跳到 kmp[j]kmp[j] 位置再试试，直到能匹配或者回跳到头为止。
  • j 与 lenb 相等时即匹配成功。

kmp 数组（好像也经常叫 next/fail 数组～～（敢用关键字 next 不是找死么）~~）：

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。

kmp[i]kmp[i] 即表示 以 b [i] 为结尾的前缀中最大 border 长度， 同时是需要回跳的位置（之后尝试匹配 j + 1 位）。

  • 用 b 串匹配自己，匹配过程中即可获取 kmp[i]kmp[i] 的值。

P3375 【模板】KMP 字符串匹配

题意：给出 a 和 b，求 b 在 a 中出现的所有起始位置，并输出 kmp 数组。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e6 + 233;
char a[MAXN], b[MAXN];
int lena, lenb, kmp[MAXN];
int main()
{
	scanf("%s%s", a + 1, b + 1);
	lena = strlen(a + 1);
	lenb = strlen(b + 1);
	// 获取 kmp (next?) 数组
	int j = 0;
	kmp[0] = kmp[1] = 0;
	for (int i = 2; i <= lenb; i++)
	{
		while (j && b[i] != b[j + 1])
			j = kmp[j];
		if (b[i] == b[j + 1])
			j++;
		kmp[i] = j; //j 结尾的前缀，与 i 结尾的一段相同，即 border
	}
    // 匹配文本串
	j = 0;
	for (int i = 1; i <= lena; i++)
	{
		while(j && a[i] != b[j + 1]) // 失配则回跳
			j = kmp[j];
		if (a[i] == b[j + 1])
			j++;
		if (j == lenb) // 匹配成功
		{
			printf("%d\n", i - lenb + 1);
			j = kmp[j]; // 回跳一下继续往后匹配
		}
	}
	for (int i = 1; i <= lenb; i++)
		printf("%d ", kmp[i]);
	return 0;
}
ex: 递推找出公共前后缀数量 P2375 [NOI2014] 动物园
nums[0] = 0,  nums[1] = 1;
for (int i = 2; i <= len; i++)
{
	while (j && str[j + 1] != str[i])
		j = kmp[j];
	if (str[j + 1] == str[i])
		j++;
	kmp[i] = j;
	nums[i] = nums[j] + 1;
}
//abacdaba    aaaaa
//11211223    12345
/*ex: 要求前后缀不能重叠 */
j = 0;
for (int i = 2; i <= len; i++)
{
	while (j && str[j + 1] != str[i])
		j = kmp[j];
	if (str[j + 1] == str[i])
		j++;
	while ((j << 1) > i) // 超过一半回跳保证不重叠
		j = kmp[j];
	num[i] = nums[j];
}
//aaaaa 01122
# manacher 最长回文子串
P3805 【模板】manacher 算法
给出一个字符串，求其中的最长回文子串。
核心思想就是利用回文串的对称性先进行一部分扩展。
首先在每两个字符之间插入一个 # 来保证每个串都有一个回文中心方便后续操作。
一些变量与解释： maxr 当前已知的回文串中所能到达的最右边界（不含）， mid 这个串的对称中心， hw[i] 位置为 i 为中心的最大回文半径。
详见注释：
int manacher()
{
    // 提前预处理好，加上井号
    rep(i, 1, n - 1)
    {
        if (i < maxr) // 当前位置在一个更大的回文串中，利用对称性更新
        {
            int j = (mid << 1) - i; // 左边关于中心对称的位置
            hw[i] = min(hw[j], hw[mid] + mid - i); // 防止超出最大边界（不能超过 maxr）
        }
        else
            hw[i] = 1; // 新的位置，默认半径为 1
        while (s[i - hw[i]] == s[i + hw[i]]) // 利用对称性初始化之后，继续往两侧扫
        {
            hw[i]++;
        }
        if (hw[i] + i > maxr) // 是否可以更新右边界
        {
            maxr = hw[i] + i;
            mid = i;
        }
        ans = max(ans, hw[i]);
    }
}