集训的第二天圆满的结束

今天主攻字符串进阶，算法包括Hash（哈希表）字符串、Manacher（俗称“马拉车”）算法、KMP算法和最小表示法

也许是学历浅薄，只掌握了Hash字符串一种算法

哈希表属于数据结构，因数值及较大要用unsigned long long数组存储（且因“ULL”的数据范围特殊，可自动对数据取模

2^{64}-1

）

算法优化的是字符串比较问题，STL库中字符串比较只有 $O(n)$ 的时间复杂度），但是通过哈希表预处理可以达到接近 $O(1)$ 的时间复杂度。

该算法的核心是以字符串的数据映射出一个数字，存入数组中，因字符串中字符较多，所以我们采取与数学中常用的十进制相似的N进制，并用另外一个数组把各个数位的进位存入以便查询(如十进制中的 $10,100,1000$ 等)

初始化

p

数组（进制数组）代码如下：

CPP

#define ull unsigned long long
#define maxn (int)(4*(1e5)+10)
const ull P = 131;
ull f[maxn], p[maxn];
int main()
{
	p[0] = 1;
	for(int i = 1;i < maxn; ++i)
	{
		p[i] = p[i-1] * P;
	}
}

我们获取到了字符串，存入Hash表的代码如下

f

数组反映的是

f[i]

与上个数据

（f[i-1]）

的关系：

CPP

for(int i = 1;i <= len; ++i)
{
    f[i] = f[i-1] * P + (s[i] - 'a' + 1);
}

此时，判断字符串是否完全相等只需要取出该字符串的Hash值相互比较：

CPP

if(f[i] == f[len] - f[len-i] * p[i])
    flag = 1;

字符串算法介绍

文章操作

集训的第二天圆满的结束

算法优化的是字符串比较问题，STL库中字符串比较只有 $O(n)$ 的时间复杂度），但是通过哈希表预处理可以达到接近 $O(1)$ 的时间复杂度。

该算法的核心是以字符串的数据映射出一个数字，存入数组中，因字符串中字符较多，所以我们采取与数学中常用的十进制相似的N进制，并用另外一个数组把各个数位的进位存入以便查询(如十进制中的 $10,100,1000$ 等)

熟练掌握以上代码，可以再刷几道例题巩固一下记忆

焦作一中OJ：

- A. 「一本通 2.1 例 2」图书管理

- B. 「一本通 2.1 练习 1」Power Strings

- C. 「一本通 2.1 练习 2」Seek the Name, Seek the Fame

洛谷：

- P3370 【模板】字符串哈希

- P5270 无论怎样神树大人都会删库跑路

- P5537 【XR-3】系统设计

以上是Hash 和今天掌握的全部内容

相关推荐

评论

字符串算法介绍

文章操作

集训的第二天圆满的结束

算法优化的是字符串比较问题，STL库中字符串比较只有O(n)O(n)O(n)的时间复杂度），但是通过哈希表预处理可以达到接近O(1)O(1)O(1)的时间复杂度。

熟练掌握以上代码，可以再刷几道例题巩固一下记忆

焦作一中OJ：

- A. 「一本通 2.1 例 2」图书管理

- B. 「一本通 2.1 练习 1」Power Strings

- C. 「一本通 2.1 练习 2」Seek the Name, Seek the Fame

洛谷：

- P3370 【模板】字符串哈希

- P5270 无论怎样神树大人都会删库跑路

- P5537 【XR-3】系统设计

以上是Hash 和今天掌握的全部内容

相关推荐

评论

算法优化的是字符串比较问题，STL库中字符串比较只有 $O(n)$ 的时间复杂度），但是通过哈希表预处理可以达到接近 $O(1)$ 的时间复杂度。