PAT--1040. Longest Symmetric String

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

题解

查找最长回文字串，扫描一遍，对每个s[i]，向左右延伸判断是否是一个回文字串。

#include <bits/stdc++.h> using namespace std; string s; int sym(int k){ int odd = 0, even = 0; int i = k, j = k; while(i >= 0 && j < s.length() && s[i] == s[j]) i--, j++, odd++; i = k, j = k + 1; while(i >= 0 && j < s.length() && s[i] == s[j]) i--, j++, even++; return max(2 * odd - 1, 2 * even); } int main(){ #ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); #endif // ONLINE_JUDGE // Is PAT&TAP symmetric? getline(cin, s); int ans = 0; for(int i = 0; i < s.length(); ++i) ans = max(ans, sym(i)); cout << ans << endl; return 0; }