## 【日常小测】友好城市

### Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ];
struct Query{
int l, r, blk, id;
inline bool operator < (const Query &Q) const {
return blk < Q.blk || (blk == Q.blk && r < Q.r);
}
}qy[QQ];
struct Bitset{
UI v[5];
inline void flip(int x) {
v[x >> 5] ^= 1 << (x & 31);
}
inline void set(int x) {
v[x >> 5] |= 1 << (x & 31);
}
inline void reset() {
memset(v, 0, sizeof(v));
}
inline bool operator [](int x) {
return v[x >> 5] & (1 << (x & 31));
}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

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

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
a1[u].set(v);
a2[v].set(u);
}

class Kosaraju{
vector<int> que;
Bitset vis;
public:
inline int solve() {
vis.reset();
que.clear();
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs0(i);
}
}
vis.reset();
int ret = 0;
for (int j = n - 1; ~j; j--) {
int i = que[j];
if (!vis[i]) {
int cnt = dfs1(i);
ret += cnt * (cnt - 1) / 2;
}
}
return ret;
}
private:
inline void dfs0(int w) {
vis.flip(w);
for (int i = 0; i < 5; i++) {
for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
int t = (__builtin_ffs(j) - 1) | (i << 5);
if (!vis[t]) {
dfs0(t);
}
}
}
que.push_back(w);
}
inline int dfs1(int w) {
vis.flip(w);
int ret = 1;
for (int i = 0; i < 5; i++) {
for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
int t = (__builtin_ffs(j) - 1) | (i << 5);
if (!vis[t]) {
ret += dfs1(t);
}
}
}
return ret;
}
}scc;

int main() {
freopen("friend.in", "r", stdin);
freopen("friend.out", "w", stdout);
for (int i = 1; i <= m; i++) {
AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
}
for (int i = 1; i <= q; i++) {
qy[i].blk = qy[i].l / BlockSize;
qy[i].id = i;
}
sort(qy + 1, qy + 1 + q);
Bitset CurG[N], CurRG[N];
for (int i = 1, L = 1, R = 0; i <= q; i++) {
if (qy[i].blk != qy[i - 1].blk || i == 1) {
L = qy[i].blk + 1;
R = L - 1;
for (int j = 1; j <= n; j++) {
CurG[j].reset();
CurRG[j].reset();
}
}
if (qy[i].r / BlockSize - 1 > R) {
for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
for (int k = 1; k <= n; k++) {
for (int h = 0; h < 5; h++) {
CurG[k].v[h] ^= PreG[j][k].v[h];
CurRG[k].v[h] ^= PreRG[j][k].v[h];
}
}
}
R = qy[i].r / BlockSize - 1;
}
if (L <= R) {
for (int i = 1; i <= n; i++) {
g[i] = CurG[i];
rg[i] = CurRG[i];
}
for (int l = qy[i].l; l < L * BlockSize; l++) {
}
for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
}
ans[qy[i].id] = scc.solve();
} else {
for (int i = 1; i <= n; i++) {
g[i].reset();
rg[i].reset();
}
for (int j = qy[i].l; j <= qy[i].r; ++j) {
}
ans[qy[i].id] = scc.solve();
}
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
return 0;
}


## 【BZOJ 3577】玩手机

### Code

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

const int INF = 1e9;
const int N = 500000;
const int M = 2000000;

int S,T,E,tot,A,B,Y,X,n2[2][70][70][8];

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;
}

inline void AddEdge(int u, int v, int f) {
assert(u); assert(v);
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class NetworkFlow{
int dis[N],cur[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis, 60, sizeof(dis));
dis[S] = 0;
for (que.push(S); !que.empty(); que.pop()) {
int w = que.front();
for (int i = head[w]; i; i = nxt[i]) {
if (flow[i] && dis[to[i]] > INF) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] <= INF;
}
inline int DFS(int w, int f) {
if (w == T) {
return f;
} else {
int ret = 0;
for (int &i = cur[w]; i; i = nxt[i]) {
if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp;
flow[i] -= tmp; flow[i ^ 1] += tmp;
if (!f) {
break;
}
}
}
return ret;
}
}
}Dinic;

int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
S = ++tot; T = ++tot;
E = 1;
for (int i = 1; i <= X; ++i) {
for (int j = 1; j <= Y; ++j) {
n1[0][i][j] = ++tot;
n1[1][i][j] = ++tot;
}
}
for (int i = X; i; --i) {
for (int j = Y; j; --j) {
for (int a = 0, len = 1; i + len - 1 <= X && j + len - 1 <= Y; ++a, len <<= 1) {
n2[0][i][j][a] = ++tot;
n2[1][i][j][a] = ++tot;
if (!a) {
} else {
int llen = len >> 1;
AddEdge(n2[0][i][j][a], n2[0][i + llen][j][a - 1], INF);
AddEdge(n2[0][i][j][a], n2[0][i][j + llen][a - 1], INF);
AddEdge(n2[0][i][j][a], n2[0][i + llen][j + llen][a - 1], INF);

AddEdge(n2[1][i][j + llen][a - 1], n2[1][i][j][a], INF);
AddEdge(n2[1][i + llen][j][a - 1], n2[1][i][j][a], INF);
AddEdge(n2[1][i + llen][j + llen][a - 1], n2[1][i][j][a], INF);
}
}
}
}
for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= A; ++i) {
p0 = ++tot; p1 = ++tot;

int len = x2 - x1 + 1, lg = 0, d = 1;
for (; (d << 1) <= len; lg++, d <<= 1);
AddEdge(p1, n2[0][x1][y2 - d + 1][lg], INF);
AddEdge(p1, n2[0][x2 - d + 1][y1][lg], INF);
AddEdge(p1, n2[0][x2 - d + 1][y2 - d + 1][lg], INF);
}
for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= B; ++i) {
p0 = ++tot;	p1 = ++tot;

int len = x2 - x1 + 1, lg = 0, d = 1;
for (; (d << 1) <= len; lg++, d <<= 1);
AddEdge(n2[1][x1][y2 - d + 1][lg], p0, INF);
AddEdge(n2[1][x2 - d + 1][y1][lg], p0, INF);
AddEdge(n2[1][x2 - d + 1][y2 - d + 1][lg], p0, INF);
}
assert(tot < N);
assert(E < M);
printf("%d\n", Dinic.MaxFlow());
return 0;
}


## 【BZOJ 2006】[NOI2010] 超级钢琴

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

const int N = 500000+9;
const int M = 20000000+9;
const int BAS = 500000010;
const int INF = 1000010000;

int n,k,L,R,arr[N];
struct Query{
int pos,num,val;
bool operator < (const Query & B) const {
return val < B.val;
}
};
priority_queue<Query> que;

namespace Chair_Tree{
#define CT Chair_Tree
int ch[M][2],sum[M],cnt,root[N],ans_tmp;

void insert(int p, int &w, int l, int r, int v) {
w = ++cnt; sum[w] = sum[p] + 1;
memcpy(ch[w],ch[p],sizeof(ch[0]));
if (l < r) {
int mid = l + r + 1 >> 1;
if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
else insert(ch[p][1], ch[w][1], mid, r, v);
}
}

inline void insert(int p, int w) {
insert(root[p-1], root[p], 1, INF, w);
}

void query(int p, int w, int l, int r, int num) {
if (l == r) ans_tmp = l;
else {
int mid = l + r + 1 >> 1;
if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num);
else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]]));
}
}

inline int query(int l, int r, int num) {
query(root[l-1],root[r],1,INF,num);
return ans_tmp;
}
};

char c=getchar(); int ret=0,f=1;
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 main(){
for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read();
for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS);
for (int i=1;i+L-1<=n;i++) {
Query tmp; tmp.pos = i; tmp.num = 1;
tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1];
que.push(tmp);
}

LL vout = 0;
for (int i=1,p;i<=k;i++) {
Query tmp = que.top(); que.pop();
vout += tmp.val;
if (tmp.num < R - L + 1) {
tmp.num++; p = tmp.pos;
if (n - (p+L-1) + 1 < tmp.num) continue;
tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS;
que.push(tmp);
}
}
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 4516】[SDOI2016] 生成魔咒

1) SAM：

SAM本身就是增量构造，于是就成裸题了

2) SA：

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

const int N = 200000+9;

char c=getchar(); int ret=0,f=1;
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;
}

namespace Suffix_Automaton{
#define SAM Suffix_Automaton
int len[N],fail[N],cnt,tail;
unordered_map<int,int> ch[N];

inline int Extend(int c) {
int w = tail; tail = ++cnt; len[tail] = len[w] + 1;
while (w&&!ch[w]) ch[w] = cnt, w = fail[w];
if (!w) fail[tail] = 1;
else {
if (len[ch[w]] == len[w]+1) fail[tail] = ch[w];
else {
int to = ch[w]; ch[++cnt] = ch[to];
fail[cnt] = fail[to]; fail[to] = cnt; fail[tail] = cnt;
len[cnt] = len[w] + 1; while (ch[w] == to) ch[w] = cnt, w = fail[w];
}
} return len[tail] - len[fail[tail]];
}

inline void solve(int n) {
cnt = tail = 1;
for (LL i=1,vout=0;i<=n;i++)
}
};

int main(){
return 0;
}


—– UPD 2016.9.29 —–

## 【BZOJ 4569】[SCOI2016] 萌萌哒

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

const int N = 100000+9;
const int MOD = 1000000007;

int n,m,fa[18][N],vout=1;

inline int find(int p, int w) {
int f = fa[p][w], tmp;
while (f != fa[p][f]) f = fa[p][f];
while (w != f) tmp = fa[p][w], fa[p][w] = f, w = tmp;
return f;
}

char c=getchar(); int ret=0,f=1;
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;
}

void merge(int t, int a, int b){
int t1 = find(t,a), t2 = find(t, b);
if (t1 == t2) return; fa[t][t1] = t2;
if (!t) return; t--, merge(t,a,b), merge(t,a+(1<<t),b+(1<<t));
}

int main(){
n = read(); m = read(); if (n == 1) return puts("10"), 0;
for (int j=0;j<=17;j++) for (int i=1;i<=n;i++) fa[j][i] = i;
for (int i=1,a,b,c,d,stp;i<=m;i++)
merge(stp,a,c), merge(stp,b-(1<<stp)+1,d-(1<<stp)+1);
for (int i=1,tag=1;i<=n;i++) if (find(0,i) == i) vout = vout*(tag?9LL:10LL) % MOD, tag = 0;
return printf("%d\n",vout), 0;
}


## 【UOJ 213】[UNR #1] 争夺圣杯

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

const int MAXN = 1000000+9;
const int MOD = 998244353;

int n,arr[MAXN],vout,que[MAXN],lft[MAXN],MX[MAXN],BUF[MAXN];

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

inline void prework(){
int tot = 0;
for  (int i=1;i<=n;i++) {
while (tot && arr[que[tot]] < arr[i]) tot--;
BUF[1] = (BUF[1]+arr[i])%MOD;
BUF[i-que[tot]+1] = ((BUF[i-que[tot]+1] - arr[i]) % MOD + MOD ) %MOD;
lft[i] = i-que[tot]; que[++tot] = i;
} tot = 0; que[0] = n+1;
for (int i=n;i;i--) {
while (tot && arr[que[tot]] <= arr[i]) tot--;
if(tot) {
BUF[que[tot]-i+1] = ((BUF[que[tot]-i+1]-arr[i]) % MOD + MOD) % MOD;
BUF[que[tot]-i+lft[i]+1] = (BUF[que[tot]-i+lft[i]+1] + arr[i]) % MOD;
} que[++tot] = i;
}
for (int i=n;i;i--) MX[i] = max(MX[i+1], arr[i]);
}

inline void solve(){
int tmp = 0, delta = 0;
for (int i=1;i<=n;i++) {
delta = ((delta + BUF[i]) % MOD + MOD) % MOD;
tmp = ((tmp + delta) % MOD + MOD) % MOD;
vout ^= tmp;
tmp -= MX[n-i+1];
}
}

int main(){
for (int i=1;i<=n;i++) arr[i] = read();
prework(); solve();
printf("%d\n",vout);
return 0;
}


## 【NOI六连测】[D2T1] 矩阵

Ⅰ.Sparse_Table版本http://paste.ubuntu.com/18292055/

Ⅱ.前缀和版本http://paste.ubuntu.com/18292096/

Ⅲ.常规矩阵Hashhttp://paste.ubuntu.com/18292122/

#include<iostream>
#include<cstdio>
#include<algorithm>
#define UL unsigned long long
using namespace std;

const int MAXN = 500+9;
const int N = MAXN*MAXN;
const UL P = 131313131;
const UL Q = 49999;

int n,m,lim; char pat[MAXN];
UL mat[MAXN][MAXN],PP[MAXN*2],QQ[MAXN*2],tmp[N];

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

inline UL GetHash(int x, int y, int L){
UL ret = 0;
ret = mat[x][y] + mat[x+L][y+L];
ret -= mat[x+L][y] + mat[x][y+L];
return ret*PP[1000-y]*QQ[1000-x];
}

inline void init(){
UL p=P,q; lim = min(n,m);
for (int j=1;j<=m;j++){
scanf("%s",pat+1);
q = Q;
for (int i=1;i<=n;i++,q*=Q)
mat[i][j] = (UL)pat[i]*q*p;
p *= P;
}
for (int i=n;i;i--) for (int j=m;j;j--)
mat[i][j] += mat[i+1][j]+mat[i][j+1]-mat[i+1][j+1];
QQ[1] = Q; PP[1] = P;
for (int i=2;i<=1000;i++)
QQ[i] = QQ[i-1]*Q,
PP[i] = PP[i-1]*P;
}

inline bool judge(int L){
int cnt = 0;
for (int i=1;i<=n-L+1;i++)
for (int j=1;j<=m-L+1;j++)
tmp[++cnt] = GetHash(i,j,L);
sort(tmp+1,tmp+1+cnt);
int tot = unique(tmp+1,tmp+1+cnt) - tmp - 1;
}

int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
init();
int l=1,r=lim,mid,vout=0;
while (l <= r){
mid = (l+r)/2;
if (judge(mid)) l = mid+1, vout = mid;
else r = mid - 1;
}
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;
}