字符串hash---CodeForces - 7D
程序员文章站
2022-06-13 11:29:55
...
题意:长度是 n 的字符串 s,如果它自身是回文数,且它的长度为 floor(n / 2)的前缀和后缀是 (k - 1)-回文数,则它被称作 k-回文数。按照定义,任何字符串 (甚至空字符串) 都是 0-回文数。
字符串 s 的回文度,被定义为这样的一个最大数 k,满足 s 是 k-回文数。例如,"abaaba" 具有的回文度是 3 。
给定一个字符串。您的任务是,找出它的全部前缀的回文度之和。
题解:dp,如果长度为i的前后缀是回文数,那么dp[i] = dp[i >> 1] + 1
那么需要解决的就是如何判断是否是回文,可以hash。
hash,只要完成一个双射即可,这就要求“基数”是质数,从左往右加和从右往左加类比数字的进位
字符串hash的恶补资料:https://blog.csdn.net/pengwill97/article/details/80879387
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=5000010;
int hash_1[maxn],hash_2[maxn];
char s[maxn];
int num[maxn],dp[maxn];
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
hash_1[0]=hash_2[0]=0;
int dig=1;
int sum=0;
int p=67;
for(int i=1;i<=len;i++){
if(s[i]>='0'&&s[i]<='9'){
num[i]=s[i]-'0';
}
else if(s[i]>='a'&&s[i]<='z'){
num[i]=s[i]-'a'+10;
}
else {
num[i]=s[i]-'A'+36;//最大的数是61,所以p=67的来源就是不小于61的最小质数
}
hash_1[i]=hash_1[i-1]*p+num[i];//将p进制数化为十进制数
hash_2[i]=hash_2[i-1]+num[i]*dig;//同上,但是数位的权值相反
dig*=p;//将hash_2的权值增加
if(hash_1[i]==hash_2[i]){//因为p是质数,说明前缀i是肯定回文(同一个数数位权值相反转化的数的值相同)
dp[i]=dp[i>>1]+1;
sum+=dp[i];
}
}
printf("%d\n",sum);
return 0;
}
// /\ | / |**、
// / \ | / | \
// / \ |/ | / _____ ____ | /
// /------\ |\ |__/ / \ \ /\ / / \ | /
// / \ | \ | / \ \ / \ / /______\ |/
// / \ | \ | \ / \ / \ / \ |
// / \ | \ | \_____/ \/ \/ \_____ |
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ > < ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//
上一篇: Three.js使用canvas样式化粒子(代码实例)
下一篇: 物联网MQTT实战