[Leetcode] Longest Palindromic Substring

 

Longest Palindromic SubstringNov 11 '116971 / 22796

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

» Solve this problem

土方法，N^2

貌似有N的方法：http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

 

class Solution {
public:
    int n;
    string longestPalindrome(string s) {
        n  = s.size();
        int m = 1, l = 0;
        for (int i = 0; i < n; i++) {
            int t = 2*maxAt(s, i)+1;
            if (t > m) {
                m = t;
                l = i - t / 2;
            }
        }
        for (int i = 0; i < n - 1; i++) {
            int t = 2 * maxAt(s, i, i+1);
            if (t > m) {
                m = t;
                l = i - t / 2 + 1;
            }
        }
        return s.substr(l, m);
    }
    int maxAt(string s, int k, int kk) {
        int i = k, j = kk;
        while (i >= 0 && j < n && s[i] == s[j]) i--, j++;
        return j - kk;
    }
    int maxAt(string s, int k) {
        int i = k , j = k;
        while (i >= 0 && j < n && s[i] == s[j]) i--, j++;
        return j - k - 1;
    }
};