## 【BZOJ 3103】[ONTAK2010] Palindromic Equivalence

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = N << 1;
const int MOD = 1000000007;

char pat[N],s[N];
int n,ans=1,fa[N],rid[N],col[N];
vector<pair<int,int> > e;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int find(int x) {
return x == fa[x]? x: fa[x] = find(fa[x]);
}

inline void manacher() {
for (int i=1,r=1,p=1,t;i<=n*2;i++) {
t = min(r - i, rid[p - (i - p)]);
while (s[i+t+1] == s[i-t-1]) t++, fa[find(i+t)] = find(fa[i-t]);
if ((rid[i] = t) + i > r) r = t + i, p = i;
e.push_back(make_pair(i - t - 1, i + t + 1));
}
}

inline void AddEdge(int u, int v) {
static int E = 1;
if (u == v || !(u & 1) || !(v & 1)) return;
}

int main() {
scanf("%s",pat+1); n = strlen(pat+1);
s[0] = '#'; s[n*2] = '@';
for (int i=1;i<=n;i++) s[i*2-1] = pat[i], s[i*2] = '*';
for (int i=1;i<=n*2;i++) fa[i] = i;
manacher();
for (int i=1,cnt;cnt=26,i<=n*2;i+=2) {
if (find(i) != i) continue; col[i] = 1;
if (col[to[j]] && vis[to[j]] < i)
--cnt, vis[to[j]] = i;
}
if (cnt <= 0) ans = 0;
else ans = (LL)ans * cnt % MOD;
}
cout<<ans;
return 0;
}


—————————— UPD 2017.4.26 ——————————

## 【BZOJ 1414】[ZJOI2009] 对称的正方形

Hash version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MX = 0;
const int MAXN = 2000+9;
unsigned int SEEDX = 37;
unsigned int SEEDY = 137;

int n,m; LL vout;
unsigned int px[2000+9],py[2000+9],mat[MAXN][MAXN],f[5][MAXN][MAXN];

char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}

inline void init(){
for (int j=1;j<=m;j++) {
for (int i=1;i<=n*2+1;i++) mat[i][j*2-1] = MX;
for (int i=1;i<=n;i++) mat[i*2][j*2] = read(), mat[i*2-1][j*2] = MX;
mat[n*2+1][j*2] = MX;
} for (int i=1;i<=n*2+1;i++) mat[i][m*2+1] = MX;
n = n*2+1; m = m*2+1;
}

inline void Hash_init(){
px[0] = 1; for (int i=1;i<=2001;i++) px[i] = SEEDX*px[i-1];
py[0] = 1; for (int i=1;i<=2001;i++) py[i] = SEEDY*py[i-1];
for (int i=n,g=1;i;i--,g++) for (int j=1,h=1;j<=m;j++,h++) f[1][i][j] = px[g]*py[h]*mat[i][j] + f[1][i+1][j] + f[1][i][j-1] - f[1][i+1][j-1];
for (int i=1,g=1;i<=n;i++,g++) for (int j=1,h=1;j<=m;j++,h++) f[2][i][j] = px[g]*py[h]*mat[i][j] + f[2][i-1][j] + f[2][i][j-1] - f[2][i-1][j-1];
for (int i=1,g=1;i<=n;i++,g++) for (int j=m,h=1;j;j--,h++) f[3][i][j] = px[g]*py[h]*mat[i][j] + f[3][i-1][j] + f[3][i][j+1] - f[3][i-1][j+1];
for (int i=n,g=1;i;i--,g++) for (int j=m,h=1;j;j--,h++) f[4][i][j] = px[g]*py[h]*mat[i][j] + f[4][i+1][j] + f[4][i][j+1] - f[4][i+1][j+1];
}

inline unsigned int Get_Hash(int t, int x1, int y1, int x2, int y2){
if (t == 1) return (f[1][x1][y1] + f[1][x2+1][y2-1] - f[1][x2+1][y1] - f[1][x1][y2-1]) * px[2001-(n-x1+1)] * py[2001-y1];
else if (t == 2) return (f[2][x1][y1] + f[2][x2-1][y2-1] - f[2][x2-1][y1] - f[2][x1][y2-1])* px[2001-x1] * py[2001-y1];
else if (t == 3) return (f[3][x1][y1] + f[3][x2-1][y2+1] - f[3][x2-1][y1] - f[3][x1][y2+1]) * px[2001-x1] * py[2001-(m-y1+1)];
else return (f[4][x1][y1] + f[4][x2+1][y2+1] - f[4][x2+1][y1] - f[4][x1][y2+1]) * px[2001-(n-x1+1)] * py[2001-(m-y1+1)];
}

inline bool judge(int x, int y, int len){
unsigned int t1 = Get_Hash(1,x,y,x+len,y-len),t2 = Get_Hash(2,x,y,x-len,y-len);
if (t1 != t2) return false;
t1 = Get_Hash(3,x,y,x-len,y+len);
if (t1 != t2) return false;
t2 = Get_Hash(4,x,y,x+len,y+len);
if (t1 != t2) return false;
else return true;
}

inline void solve(){
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i&1) + (j&1) != 1) {
int l=2,r=min(min(i-1,j-1),min(n-i,m-j)),ans=0,mid;
while (l <= r) {
mid = l + r >> 1;
if (judge(i,j,mid)) l = mid+1, ans = mid;
else r = mid-1;
}vout += ans/2;
}
}

int main(){
init(); Hash_init(); solve();
printf("%lld\n",vout);
return 0;
}


Manacher version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 2000+9;

int mat[MAXN][MAXN],n,m,tmp[MAXN],ans[MAXN],que[MAXN],tot,pos[MAXN];
int res_x[MAXN][MAXN],res_y[MAXN][MAXN],sa_y[MAXN][MAXN],sa_x[MAXN][MAXN];

char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}

inline void manacher(int lim){
int MX=0; ans[0] = 0;
for (int i=1;i<=lim;i++) {
if (MX+ans[MX] > i) ans[i] = min(MX+ans[MX]-i, ans[MX*2-i]);
else ans[i] = 0;
while (tmp[i+ans[i]+1] == tmp[i-ans[i]-1]) ans[i]++;
if (ans[i]+i > MX+ans[MX]) MX = i;
}
}

inline void DP(int lim){
tot = 0; pos[0] = 0; int sta = 0;
for (int i=1;i<=lim;i++) {
while (tot && ans[i] <= que[tot]) tot--; sta = min(sta, tot);
que[++tot] = ans[i]; pos[tot] = i; int w = sta;
while (w < tot && min(que[w],(i-pos[w-1])*2-1) <= min(que[w+1],(i-pos[w])*2-1)) w++;
sta = w; tmp[i] = min(que[w],(i-pos[w-1])*2-1);
}
}

int main(){
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) mat[i*2][j*2] = read();
n = n * 2 + 1; m = m * 2 + 1;

for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) tmp[j] = mat[i][j]; tmp[0] = -1; tmp[m+1] = -2;
manacher(m);
for (int j=1;j<=m;j++) sa_y[i][j] = ans[j];
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) ans[i] = sa_y[i][j]*2+1;
DP(n);
for (int i=1;i<=n;i++) res_x[i][j] = tmp[i];
for (int i=1;i*2<=n;i++) swap(ans[i],ans[n-i+1]);
DP(n);
for (int i=1;i<=n;i++) res_x[i][j] = min(res_x[i][j],tmp[n-i+1]);
}

for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) tmp[i] = mat[i][j]; tmp[0] = -1; tmp[n+1] = -2;
manacher(n);
for (int i=1;i<=n;i++) sa_x[i][j] = ans[i];
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) ans[j] = sa_x[i][j]*2+1;
DP(m);
for (int j=1;j<=m;j++) res_y[i][j] = tmp[j];
for (int j=1;j*2<=m;j++) swap(ans[j],ans[m-j+1]);
DP(m);
for (int j=1;j<=m;j++) res_y[i][j] = min(res_y[i][j], tmp[m-j+1]);
}

LL vout = (n/2)*(m/2);
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i+j) % 2 == 0)
vout += max(0,(min(res_x[i][j]-1,res_y[i][j]-1)/2)/2);
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 2342】[Shoi2011] 双倍回文

manacher自己做的第一题！ 2A！ 撒花！ *★,°*:.☆\(￣▽￣)/$:*.°★* 最开始看这个题：树套树？二维偏序的既视感……然而树套树求取区间最值的空间复杂度绝对过不了 于是可耻看题解，瞄了一眼：用set就可以水掉QAQ 于是再自己推一推，确定两个set连起来就可以搞 搞一搞520ms水过去了 再一看题解，还可以只用一个set水过去QAQ 不过跑出来反而比hzwer的一个set快一点…….. #include<iostream> #include<cstdio> #include<cstring> #include<set> using namespace std; const int MAXN = 1200000; char pat[MAXN],BUF[MAXN]; int p[MAXN],rt,n,len,vout; inline void manacher(){ len = n*2+1; for (int i=1,p1,p2;i<=len;i++){ if (p[rt]+rt > i) p[i] = min(p[rt*2-i],p[rt]+rt-i); else p[i] = 0; p1 = i+p[i]; p2 = i-p[i]; while (pat[++p1] == pat[--p2]) p[i]++; if (pat[rt]+rt < p[i]+i) rt = i; } } inline void init(){ scanf("%d%s",&n,BUF+1); for (int i=1;i<=n;i++){ pat[i*2-1] = '@'; pat[i*2] = BUF[i]; } pat[n*2+1] = '@'; pat[0] = '#'; pat[n*2+2] = '$';
}

struct cmp{
bool operator () (const int &a, const int &b){
return a+p[a] < b+p[b];
}
};

set<int> por;
set<int,cmp> list;
set<int>::iterator itr;
set<int,cmp>::iterator ITR;
pair<set<int,cmp>::iterator,bool> TMP;

inline void solve(){
for (int i=3;i<=len;i+=2){
int p1 = i-p[i]/2,buf=0;
itr = por.lower_bound(p1);
if (itr != por.end()){
buf = (i-*itr+1)/2;
vout = max(vout, buf*4);
}

TMP = list.insert(i);
if (TMP.second) por.insert(i);

ITR = list.begin();
while (!list.empty() && *ITR+p[*ITR] < i+2)
por.erase(*ITR), list.erase(ITR),ITR = list.begin();
}
printf("%d",vout);
}

int main(){
init();
manacher();
solve();
return 0;
}


## 【BZOJ 3325】[Scoi2013] 密码

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int SIGMA_SIZE = 26;

struct Palindromic_Tree{
#define PAM Palindromic_Tree
int ch[MAXN][SIGMA_SIZE],fail[MAXN];
int cnt,last,n,sz[MAXN],len[MAXN];
char *pat; LL ret;

inline int newnode(){
cnt += 1;
memset(ch[cnt],0,sizeof(ch[cnt]));
fail[cnt] = sz[cnt] = len[cnt] = 0;
return cnt;
}

inline void init(){
cnt = last = 1;
fail[0] = fail[1] = 1;
sz[0] = sz[1] = len[0] = 0; len[1] = -1;
memset(ch[0],0,sizeof(ch[0]));
memset(ch[1],0,sizeof(ch[1]));
}

inline void extend(int p, int c){
int w = last;
while (pat[p-len[w]-1] != pat[p]) w = fail[w];
if (!ch[w]){
int nw = newnode(),k=fail[w]; len[nw] = len[w]+2;
while (pat[p-len[k]-1] != pat[p]) k = fail[k];
fail[nw] = ch[k]; ch[w] = nw;
}
last = ch[w];
sz[last]++;
}

inline void build(char *s){
init(); pat = s;
n = strlen(s+1);
for (int i=1;i<=n;i++)
extend(i,s[i]-'a');
for (int i=cnt;i;i--)
sz[fail[i]] += sz[i];
}

void DFS(int pa, int pb, PAM *s){
if (pa > 1 && pb > 1) ret += (LL)sz[pa]*(LL)s->sz[pb];
for (int i=0;i<SIGMA_SIZE;i++)
if (ch[pa][i] && s->ch[pb][i])
DFS(ch[pa][i],s->ch[pb][i],s);
}

inline LL solve(PAM *a){
ret = 0LL;
DFS(0,0,a);
DFS(1,1,a);
return ret;
}
}A,B;

char sa[MAXN],sb[MAXN];

int main(){
int T,TT=0; cin>>T;
while (T--){
scanf("%s%s",sa+1,sb+1);
A.build(sa); B.build(sb);
printf("Case #%d: %I64d\n",++TT,A.solve(&B));
}
return 0;
}


## 【Tsinsen 1280】最长双回文串

#include<iostream>
#include<cstdio>
#include<cstring>
#include
<map>
using namespace std;

const int MAXN = 200000+9;
char pat[MAXN],BUF[MAXN/2];
int n,len[MAXN],vout;

map<int,int>::iterator itr;
map<int,int> Q;

inline void manacher(){
int mx = 0;
for (int i=1;i<=n;i++){ if (mx+len[mx] > i) len[i] = min(len[mx*2-i],mx+len[mx]-i);
else len[i] = 0;
while (pat[i+len[i]+1] == pat[i-len[i]-1]) len[i]++;
if (len[i]+i > len[mx]+mx) mx = i;
}
}

inline void init(){
scanf("%s",BUF+1);
n = strlen(BUF+1); vout = 2;
for (int i=1;i<=n;i++){
pat[i*2-1] = '*';
pat[i*2] = BUF[i];
} pat[n*2+1] = '*';
n=n*2+1; pat[0]='@'; pat[n+1]='&';
}

inline void solve(){
for (int i=1;i<=n;i++){ itr = Q.lower_bound(i-len[i]); if (itr != Q.end()){ int p = itr->second;
vout = max(vout,i-p);
}

if ((Q.insert(make_pair(i+len[i], i))).second){
itr = Q.find(i+len[i]);
if (i >= (++itr)->second && itr != Q.end()) Q.erase(--itr);
else{
itr--;
while (itr != Q.begin() && (--itr)->second >= i) Q.erase(itr), itr=Q.find(i+len[i]);
}
}
}
}

int main(){
init();
manacher();
solve();
printf("%d\n",vout);
return 0;
}


## 【BZOJ 3676】[Apio2014] 回文串

1. 10min 确定 SA + manacher
2. 1h 码完代码
3. 6h 调试代码，BZOJ仍然超时QAQ
4. UOJ上发现原题，提交，通过！

————————————————— 我是华丽丽的分割线，下面才是正文 ———————————————————

HINT：
1.网上很多代码都有问题，比如hzwer的就可以被“abbababbbb”卡掉，正解7，hzwer输出8（他的马拉车写错了）
2.BZOJ数据太强，SA + manacher要T，不过UOJ可过（其实在manacher那里分类讨论的话，也是可以卡过的
3.会用SAM的就不要用SA做死啦（或者你要用DC3应该也是可以过的，但是我不会QAQ
4.会用回文自动机的就不要用manacher做死啦！
5.刚才都说了网上的代码可能有错，所以能过就好
6.此题必须不放过任意一个本质不同的回文串，否则正确性有问题，哎呀刚才自己出的那组数据找不到了QAQ
7.答案会爆int
Inspiration：对于manacher来说，本质不同的回文串一定是能使右边界指针向右移的串
AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 1210000;

char BUF[MAXN],pat[MAXN];
int n,rep[MAXN],LEN[MAXN];
LL vout=1;

inline void init(){
gets(BUF+1);
n = strlen(BUF+1);
for (int i=1;i<=n;i++){
pat[i*2-1] = 123;
pat[i*2] = BUF[i];
} n = n*2+1;
pat[n]=123; LEN[1] = 0;
for (int i=2;i<=n;i++)
LEN[i] = LEN[i>>1]+1;
}

namespace Suffix_Array{
#define SA Suffix_Array
#define SIGMA_SIZE 30
int sa[MAXN],bot[MAXN],t1[MAXN],t2[MAXN],*tmp,*rank;
int m,height[MAXN];

namespace Sparse_Table{
#define ST Sparse_Table
int mx[MAXN][17];

inline void init(){
for (int i=1;i<=n;i++)
mx[i][0] = height[i];
for (int i=1,len=1;len<=n;i++,len*=2){
for (int j=1;j<=n;j++)
mx[j][i] = min(mx[j][i-1],mx[j+len][i-1]);
}
}

inline int query(int l, int r){
int t=LEN[r-l+1];
return min(mx[l][t],mx[r-(1<<t)+1][t]);
}
};

inline void GetHeight(char *s){
for (int i=1,t=0;i<=n;i++){
if (t) t--;
int p1 = i+t, p2 = sa[rank[i]-1]+t;
while (s[p1++] == s[p2++]) t++;
height[rank[i]] = t;
}
pat[n+1]=125; pat[0]=124;
ST::init();
}

inline void build(char *s){
m = SIGMA_SIZE; tmp = t1; rank = t2;
for (int i=1;i<=n;i++) bot[tmp[i]=s[i]-'a'+1]++;
for (int i=2;i<m;i++) bot[i] += bot[i-1];
for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++)
if (s[sa[i]] != s[sa[i-1]]) rank[sa[i]] = ++m;
else rank[sa[i]] = m;

for (int k=1,T=0;k<=n;k*=2,T=0){
for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
for (int i=1;i<=m;i++) bot[i] = 0;
for (int i=1;i<=n;i++) bot[rank[i]]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];

swap(tmp,rank);
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++)
if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]] = m;
else rank[sa[i]] = ++m;

if (m >= n) break;
}

GetHeight(s);
}

inline int match_right(int s,int len){
int l = 1, r = n-s,ret=1;
while (l <= r){
int mid = (l + r) / 2;
if (ST::query(s+1,s+mid) >= len) ret = mid, l=mid+1;
else r = mid-1;
}
return ret;
}

inline int match_left(int s,int len){
int l = 1, r = s,ret=1;
while (l <= r){
int mid = (l + r) / 2;
if (ST::query(s-mid+1,s) >= len) ret = mid, l=mid+1;
else r = mid-1;
}
return ret;
}

inline int search(int s, int len){
int ret = 1, pos = rank[s];
if (height[pos] >= len && pos > 1) ret += match_left(pos,len);
if (height[pos+1] >= len && pos < n) ret += match_right(pos,len);
return ret;
}
};

inline void solve(int i){
int beg = i-rep[i];
int t = SA::search(beg,rep[i]*2+1);
vout = max(vout, (LL)t*(LL)rep[i]);
}

inline void manacher(){
int itr=0;
for (int i=1;i<=n;i++){
if (rep[itr]+itr > i) rep[i] = min(rep[itr*2-i],rep[itr]+itr-i);
else rep[i] = 0;
int p1 = i+rep[i], p2 = i-rep[i];
while (pat[--p2]==pat[++p1])
rep[i]++, solve(i);
if (rep[i]+i > rep[itr]+itr) itr = i;
}
printf("%lldn",vout);
}

int main(){
init();
SA::build(pat);
manacher();
return 0;
}


AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 300000+9;

char pat[MAXN];

namespace Palindromic_Tree{
#define PAM Palindromic_Tree
#define SIGMA_SIZE 26
int ch[MAXN][SIGMA_SIZE],sz[MAXN],fail[MAXN];
int n,cnt,last,len[MAXN];

inline void init(){
cnt = 1;
fail[0] = fail[1] = 1;
len[1] = -1;
}

inline void expend(int pos, int c, char *s){
int cur = last;
while (s[pos-len[cur]-1] != s[pos]) cur = fail[cur];
if (!ch[cur]){
int w = ++cnt, k = fail[cur];
len[w] = len[cur] + 2;
while (s[pos-len[k]-1] != s[pos]) k = fail[k];
fail[w] = ch[k]; ch[cur] = w;
}
last = ch[cur];
sz[last]++;
}

inline void build(char *s){
init();
n = strlen(s+1);
for (int i=1;i<=n;i++)
expend(i,s[i]-'a',s);
}

inline LL solve(){
LL ret = 1;
for (int i=cnt;i;i--){
sz[fail[i]] += sz[i];
ret = max(ret, (LL)len[i]*(LL)sz[i]);
}
return ret;
}
};

int main(){
scanf("%s",pat+1);
PAM::build(pat);
printf("%lldn",PAM::solve());
return 0;
}


## 【BZOJ 3790】神奇项链

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 120000;

char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];

namespace FenwickTree{
#define BIT FenwickTree
#define low(x) (x&(-x))
#define INF 1000000000
int arr[MAXN],buf[MAXN];

inline void init(){
for (int i=1;i<=n;i++)
arr[i] = buf[i] = INF;
}

inline int query(int left, int right){
if (right < left) return INF; else { int ret = INF; while (right >= left){
if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
else ret = min(ret,buf[right]), right--;
}
return ret;
}
}

inline void modify(int pos, int nv){
if (buf[pos] > nv) {
buf[pos] = nv;
for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
else break;
} else return;
}
};

inline bool sort_cmp(const int &A, const int &B){
return r[A] < r[B];
}

inline int manacher(){
int m=n*2+1,itr=0;
for (int i=1;i<=n;i++)
chr[i*2-1] = '@',
chr[i*2] = pat[i];
chr[m] = '@'; chr[m+1] = '#'; chr[0] = '\$';

for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i)  len[i] = min(len[2*itr-i],itr+len[itr]-i);
else len[i] = 0;
p1 = i-len[i]; p2 = i+len[i];
while (chr[--p1] == chr[++p2]) len[i]++;
if (itr+len[itr] < i+len[i]) itr = i;
}

for (int i=1;i<=m;i++)
r[i] = i+len[i],
l[i] = i-len[i],
ord[i] = i;
sort(ord+1,ord+m,sort_cmp);

n = m; BIT::init(); BIT::modify(1,0);
for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
tmp = BIT::query(l[i],r[i]-1)+1;
BIT::modify(r[i],tmp);
}

return BIT::query(m-1,m)-1;
}

int main(){
while (~scanf("%s",pat+1)){
n = strlen(pat+1);
printf("%dn",manacher());
}
return 0;
}