摘要
Title: A1040 Longest Symmetric String (25)
Tag: 回文串
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

A1040 Longest Symmetric String (25)

• 题意

  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.

• 思路

  注意这里是求子串，不是子序列！
  （如果题目是求子序列的话，可以采用，将字符串反转，再求LCS的方法）

  如果是子串的话，就枚举中心点即可，再枚举回文串的偶数长度和奇数长度

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-01-09 13:57:06
  * @FilePath: \GPLT\A1040\A1040.cpp
  * @LastEditTime: 2023-01-09 19:06:00
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int
  
  #define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int N = 1e4 + 10, INF = 0x3f3f3f3f;
  
  signed main()
  {
      IOS;
      string s;
      getline(cin, s);
      int ans = 1;
      for (int i = 0; i < SZ(s); ++i)
      {
          // odd
          int l = i - 1, r = i + 1;
          while (l >= 0 && r < SZ(s) && s[l] == s[r])
              l--, r++;
          ans = max(ans, r - l - 1);
          // even
          l = i, r = i + 1;
          while (l >= 0 && r < SZ(s) && s[l] == s[r])
              l--, r++;
          ans = max(ans, r - l - 1);
      }
      cout << ans;
      return 0;
  }