PAT (Advanced Level) Practise 1040 Longest Symmetric String (25)

1040. Longest Symmetric String (25)

時間限制

400 ms

記憶體限制

65536 kB

代碼長度限制

16000 B

判題程式

Standard

作者

CHEN, Yue

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given "Is PAT&TAP symmetric?", the longest symmetric sub-string is "s PAT&TAP s", hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

11

最長回文字串，這題可以直接暴力。我用的manacher效率o(n)

#include<cstdio>    
#include<cstring>    
#include<cmath>    
#include<algorithm>    
#include<queue>    
using namespace std;
typedef long long ll;
const int maxn = 110005;
char s[maxn], S[maxn * 2];
int f[maxn * 2];

int manacher(char *s)
{
  //字元串處理，增加分隔符
  int n = strlen(s);
  S[n + n + 2] = 0; S[0] = 2;
  for (int i = 0; s[i]; i++)
  {
    S[i + i + 3] = S[i + i + 1] = 1;
    S[i + i + 2] = s[i];
  }

  //manacher算法，計算出以每個字元為中心的最長回文串
  int mx = 0, id = 0, ans = 0;
  for (int i = 1; S[i]; i++)
  {
    if (mx > i) f[i] = min(f[id + id - i], mx - i);
    else f[i] = 1;
    while (S[i + f[i]] == S[i - f[i]]) f[i]++;
    if (f[i] + i > mx)
    {
      mx = f[i] + i;
      id = i;
    }
    ans = max(ans, f[i] - 1);
  }
  return ans;
}

int main()
{
  gets(s);
  printf("%d\n", manacher(s));
  return 0;
}