Codeforces 961F: 字符串hash

xiaoxiao2021-02-28  4

题意:给一个字符串,求出其border长度(前缀=后缀,且长度最长),然后切掉第一个和最后一个字母,再求border,直到字符串切么得了。

题解:

首先要发现一个性质:设一个字符串的border长度为x,那么,在这个字符串头尾各加上一个字母,新字符串的border长度最多为x+2。

证明的话,考虑反证法:设原串border长度为x,即长度最长的前缀=后缀,假设添加字母之后,border'>x+2,那么把长度=border'的前缀平移到长度=border'的后缀上一比对,容易看出原串border长度>x,产生矛盾。

那么考虑题目所说的这个过程的反过程,就是每次添加字母,每次的添加,最多使得border+2,那么总共最多使得border增加2*n/2=O(n),然后考虑减少的,即,原串border=x,新串border'<x+2,设delta=border-border',发现这个delta总共也是O(n)的(废话,增加的总共O(n),减少的肯定也是O(n)),那么。。直接hash+暴力不就行了吗。。这样总共的check次数是O(2n)的。

注意hash姿势。。出题人精心卡掉了自然溢出的hash姿势。存在另外一种hash姿势:选择一个小质数和一个大质数,小质数作为hash的进制数字,大质数用作取模,并采取多重hash防止冲突。。。总之被卡的已经不省人事了。。主要写博客为了记录下这种hash姿势以及hash质数。。。下次被卡了就拜一下这个题。。

Code:

#include<bits/stdc++.h> using namespace std; const int maxn = 1e6+100; const int HASH_NUM = 10; typedef long long LL; int AC[HASH_NUM] ={131,137,139,149,151,157,163,167,173,179}; int ACC[HASH_NUM] ={200003,200009,200017,200023,200029,200033,200041,200063,200087,200117}; LL bas[maxn][HASH_NUM]; int n; char s[maxn]; LL sum1[maxn][HASH_NUM]; int ans[maxn]; bool check(int index,int x,int len){ LL hs1 = ((sum1[x+len-1][index]-sum1[x-1][index]*bas[len][index]
转载请注明原文地址: https://www.6miu.com/read-2400387.html

最新回复(0)