一、模板
算法解析：http://www.felix021.com/blog/read.php?2040
*主要用来解决一个字符串中最长回文串的长度，在O（n）时间内，线性复杂度下，求出以每个字符串为中心的最长回文，奇数回文跟偶数回文一起考虑了
S $ # # # # # # # # #
P 最后所求的值就是max(P[i]-) //输入，并处理得到字符串s,s[0]=$
void getp()
{
int p[], mx = , id = ;
memset(p, , sizeof(p));
for (i = ; s[i] != '\0'; i++)
{
p[i] = mx>i ? min(p[*id-i], mx-i) : ;
while (s[i + p[i]] == s[i - p[i]]) p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
}
二、题目
题意：输入n(1 <= n <= 100000)个人的身高hi(50 <= hi <= 250)，从这些人中连续挑出k个人，这k个人【身高是左右对称的，如果是k是奇数，那么中间那个人的身高任意】&&【从左到中间那个人，身高需保证不下降，如果用H表示新队形的高度，则H[1] <= H[2] <= H[3] .... <= H[mid]】，求k的最大值。
解题思路：一般的manacher添加的是’#’，但是本题左半边的身高不递减，所以添加的应该是(h[i]+h[i+1])/2，注意细节。处理后的第奇数个身高是添加上去的，第偶数个身高是一开始输入的，当i-p[i]是奇数时，无论hh[i-p[i]]与hh[i+p[i]]是否相等，p[i]都应该+1。
比如：h[] = 80 60 70 60 90 50 ==> hh[] = -1 65 70 65 65 75 70 65【有颜色的是原串】，以70为中心时，p[6]=4而不是3
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int N=*1e5+;
int h[N], hh[N];
int t, n;
int p[N], lenhh;
void getp()
{
int mx = , id = ;
memset(p, , sizeof(p));
for (int i = ; i<lenhh; i++)
{
p[i] = mx>i ? min(p[*id-i], mx-i) : ;
while(hh[i + p[i]] == hh[i - p[i]] && hh[i-p[i]]<=hh[i-p[i]+]) p[i]++;
if((i-p[i])%) p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i=; i<=n; i++){
scanf("%d", &h[i]);
}
h[]=h[n], h[n+]=h[];
lenhh=;
hh[]=(h[]+h[])/, hh[]=-;
for(int i=; i<=n; i++){
hh[lenhh++]=h[i];
hh[lenhh++]=(h[i]+h[i+])/;
}
// for(int i=0; i<lenhh; i++) cout<<hh[i]<<" ";
// cout<<endl;
getp();
int maxn=;
// for(int i=0; i<lenhh; i++) cout<<p[i]<<" ";
// cout<<endl;
for(int i=; i<lenhh; i++) maxn = max(maxn, p[i]-);
printf("%d\n", maxn);
}
return ;
}
2、【HDU 3948】The Number of Palindromes(manacher +建图 || )
题意：输入一个字符串(len<=1e5)，求这个字符串中不同的回文子串的个数，如：【输入aaaa，有四个不同的回文子串，a、aa、aaa、aaaa】
解题思路：先用计算字符串的hash值，manacher算法求出p[]，枚举每一个中心点，从可能的最长回文串的两端逐渐向里判断是否出现过，如果长的出现过了，那短的也一定出现过。判断这个字符串是否出现过目前一共有两种方法：【最后的点的总数不会超过3*1e5的，那就将每一个hash值都对mod(mod=3*1e5+10)取余，建图，hash值%mod后相等的利用head连成一个图】&&【这一种方式就是比较费时但也比较直接的，直接用map判断这个hash值是不是出现过】
Get新技能：将判断字符串是否出现过转化为判断hash值是不是出现过，同时建图判断hash值是否出现过。
manacher+建图
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std; #define ull unsigned long long
#define ll __int64 const int N = 1e5+;
const ull bas = ;
ull has[N], base[N];
char s[N], ss[*N];
int lenss, p[*N]; struct hash_map{
const static int mod=*N+;//一个静态的、值不能被改变的整型常量
int idx, head[mod]; struct hash_tables{
int next;
ull key;
}ele[*N]; void init(){
idx = ;
memset(head, 0xff, sizeof(head));//初始化为-1
} void clear(){// clear的效率要高于init的效率，后期的用以替换init
for(int i=; i<idx; i++){
head[ele[i].key%mod] = -;
}
idx = ;
} void insert(ull x){
int tmp = x%mod;
ele[idx].key = x;
ele[idx].next = head[tmp];
head[tmp] = idx++;
} bool find(ull x){
int hashcode = x%mod;
for(int i=head[hashcode]; i!=-; i=ele[i].next){
if(ele[i].key == x) return true;
}
return false;
}
}hashi; // 将hash表的实现封装成一个类 ll ans; void manacher(){
int mx = , id = ;
memset(p, , sizeof(p));
for (int i = ; i<lenss; i++)
{
p[i] = mx>i ? min(p[*id-i], mx-i) : ;
while (ss[i + p[i]] == ss[i - p[i]]) p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
}
void init(){
ss[] = '$', ss[] = '#';
lenss = , has[]=;
int len=strlen(s);
for(int i=; i<len; i++){
has[i+] = has[i]*bas+s[i]-'a'+;
ss[lenss++] = s[i];
ss[lenss++] = '#';
}
ss[lenss]='\0';
manacher();
}
int begn, ed;
void find(int id, int dis){
begn=id-dis+, ed=id+dis-;
if(begn%==) begn++, ed--;
while(begn<=ed){
ull k = has[ed/] - has[begn/-]*base[ed/-begn/+];
if(!hashi.find(k)){
hashi.insert(k);
ans++;
}
else break;
begn+=, ed-=;
}
}
int main(){
int t, cas=;
scanf("%d", &t);
hashi.init();
base[] = ;
for(int i=; i<N; i++) base[i] = base[i-]*bas; while(t--){
hashi.clear();
scanf("%s", s);
init(); ans = ;
for(int i=; i<lenss; i++){
find(i, p[i]);
}
printf("Case #%d: %I64d\n", cas++, ans);
}
return ;
}
manacher+map
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std; #define ull unsigned long long const int N = 1e5+;
const ull bas = ;
ull has[N], base[N];
char s[N], ss[*N];
int lenss, p[*N];
map<ull, int>mp; int ans; void manacher(){
int mx = , id = ;
memset(p, , sizeof(p));
for (int i = ; ss[i] != '\0'; i++)
{
p[i] = mx>i ? min(p[*id-i], mx-i) : ;
while (ss[i + p[i]] == ss[i - p[i]]) p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
}
void init(){
ss[] = '$', ss[] = '#';
lenss = , has[]=;
int len = strlen(s);
for(int i=; i<len; i++){
has[i+] = has[i]*bas+s[i]-'a'+;
ss[lenss++] = s[i];
ss[lenss++] = '#';
}
ss[lenss] = '\0';
manacher();
}
int begn, ed;
void find(int id, int dis){
begn=id-dis+, ed=id+dis-;
if(begn%==) begn++, ed--;
while(begn<=ed){
ull k = has[ed/] - has[begn/-]*base[ed/-begn/+];
if(!mp[k]){
mp[k] = ;
ans++;
}
else break;
begn+=, ed-=;
}
}
int main(){
int t, cas=;
scanf("%d", &t); base[] = ;
for(int i=; i<N; i++) base[i] = base[i-]*bas; while(t--){
scanf("%s", s);
init(); ans = , mp.clear();
for(int i=; i<lenss; i++){
find(i, p[i]);
}
printf("Case #%d: %d\n", cas++, ans);
}
return ;
}