HYSBZ 3676 回文串

Description

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出 

现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最 

大出现值。 

Input

输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。 

Output

输出一个整数，为逝查回文子串的最大出现值。 

Sample Input

【样例输入l】

abacaba

【样例输入2]

www

Sample Output

【样例输出l】

7

【样例输出2]

4

Hint

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。 

在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中： 

● a出现4次，其出现值为4：1：1=4 

● b出现2次，其出现值为2：1：1=2 

● c出现1次，其出现值为l：1：l=l 

● aba出现2次，其出现值为2：1：3=6 

● aca出现1次，其出现值为1=1：3=3 

●bacab出现1次，其出现值为1：1：5=5 

● abacaba出现1次，其出现值为1：1：7=7 

故最大回文子串出现值为7。 

【数据规模与评分】 

数据满足1≤字符串长度≤300000。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
char s[maxn];

struct PalindromicTree
{
  const static int maxn = 3e5 + 10;
  const static int size = 26;
  int next[maxn][size], last, sz, tot;
  int fail[maxn], len[maxn];
  LL cnt[maxn];
  char s[maxn];
  void clear() 
  { 
    len[1] = -1; len[2] = 0;
    fail[2] = fail[1] = 1;  
    last = (sz = 3) - 1;  
    cnt[1] = cnt[2] = tot = 0;
    memset(next[1], 0, sizeof(next[1]));
    memset(next[2], 0, sizeof(next[2]));
  }
  int Node(int length)
  {
    memset(next[sz], 0, sizeof(next[sz]));
    len[sz] = length;  cnt[sz] = 0; return sz;
  }
  int getfail(int x)
  {
    while (s[tot] != s[tot - len[x] - 1]) x = fail[x];
    return x;
  }
  int add(char pos)
  {
    int x = (s[++tot] = pos) - 'a', y = getfail(last);
    if (next[y][x]) { ++cnt[last = next[y][x]]; return 0; }

    last = next[y][x] = Node(len[y] + 2);
    fail[sz] = len[sz] == 1 ? 2 : next[getfail(fail[y])][x];
    return ++cnt[last], ++sz, 1;
  }
  void work()
  {
    LL ans = 0;
    for (int i = sz-1; i > 2; i--)
    {
      cnt[fail[i]] += cnt[i];
      ans = max(ans, cnt[i] * len[i]);
    }
    printf("%lld\n", ans);
  }
}solve;

int main()
{
  while (scanf("%s", s) != EOF)
  {
    solve.clear();
    for (int i = 0; s[i]; i++) solve.add(s[i]);
    solve.work();
  }
  return 0;
}