即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

PAT–1040. Longest Symmetric String

编程语言 xushao_Movens 9℃ 0评论
本文目录
[隐藏]

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.

1.Input Specification:

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

2.Output Specification:

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

3.Sample Input:

Is PAT&TAP symmetric?

4.Sample Output:

11

5.题解

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

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

转载请注明:CodingBlog » PAT–1040. Longest Symmetric String

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情