5. Longest Palindromic Substring【字符串 DP】

class Solution {
public:
    string longestPalindrome(string s) {
    	int l = s.length();
    	bool p[1000][1000] = {false};
    	int max_len = 1 , max_beg = 0;
    	p[l-1][l-1] = true;
    	for(int i=0;i<l;i++){
    		p[i][i] = true;
    		if(s[i] == s[i+1]){
    			p[i][i+1] = true;
    			max_len = 2;
    			max_beg = i;
    		}
    	}
    	for(int length=3 ;length<=l ;length++){
    		for(int i=0;i<=l-length;i++){
    			int j = i+length-1;
    			if(s[i] == s[j] && p[i+1][j-1]){
    				p[i][j] = true;
    				max_beg = i;
    				max_len = length;
    			}
    		}
    	}
    	return s.substr(max_beg,max_len);
    }
};

def Palindromic( s , i , j ):
	l = len(s)
	curLen = 0
	while i>=0 and j<l and s[i] == s[j]:
		i -= 1
		j += 1
	curLen = (j - 1) - (i + 1) + 1
	return curLen 
class Solution(object):
    def longestPalindrome(self, s):
        start = 0
        max_len = 1
        for i in range(len(s)):
        
        	curOdd = Palindromic(s,i,i)
        	if curOdd > max_len:
        		max_len = curOdd
        		start = i - curOdd/2
        	if i+1<len(s):
        		curEven = Palindromic(s,i,i+1)
        		if curEven > max_len:
        			max_len = curEven
        			start = i + 1 - curEven/2
        return s[start:start+max_len]

public class Solution {
    public String longestPalindrome(String s) {
        //预处理
		StringBuffer sb = new StringBuffer("^#");
		for( int i=0;i<s.length();i++ ){
			sb.append(s.substring(i,i+1)+"#");
		}
		sb.append("$");
		String str = sb.toString();
		//预处理完毕
		int[] p = new int[str.length()];
		int mx = 0 , id = 0;
		for( int i=1;i<str.length()-1;i++ ){
			p[i] = mx>i ? Math.min( p[ 2*id-i ] , mx - i + 1 ) : 1;
			while( str.charAt( i+p[i] ) == str.charAt( i-p[i] )) ++p[i];
			if( p[i] > p[id] ) {
				id = i;
				mx = i + p[i] - 1;
			}
		}
		return s.substring( (2 * id - mx - 1) / 2  , (mx-1)/2 );
    }
}