C solution using Manacher's algorithm (3ms)


  • 0
    L
    #define MIN(x, y)		((x) < (y)) ? (x) : (y)
    #define MAX_LEN			1000
    #define MANACHER_LEN(len)	((len) * 2 + 3)
    #define MAX_MANACHER_LEN	MANACHER_LEN(MAX_LEN)
    #define MANACHER_START_CHAR	'^'
    #define MANACHER_SPECIAL_CHAR	'#'
    #define MANACHER_END_CHAR	'$'
    
    char* longestPalindrome(char* s) {
    	int slen = strlen(s);
    	if (slen <= 1)
    		return s;
    
    	/*
    	*  Convert T string from S string,
    	*  for example, S = "abaaba", T = "^#a#b#a#a#b#a#$"
    	*/
    	char T[MAX_MANACHER_LEN];
    	int tlen = MANACHER_LEN(slen);
    	T[0] = MANACHER_START_CHAR;
    	T[1] = MANACHER_SPECIAL_CHAR;
    	for (int i = 0, j = 2; i < slen; i++, j+=2) {
    		T[j] = s[i];
    		T[j + 1] = MANACHER_SPECIAL_CHAR;
    	}
    	T[tlen - 1] = MANACHER_END_CHAR;
    
    	/*
    	*  Manacher's algorithm
    	*  Reference: https://articles.leetcode.com/longest-palindromic-substring-part-ii
    	*/
    	unsigned short P[MAX_MANACHER_LEN];
    	int C = 0, R = 0;
    	int center_idx = 0, max_len = 0;
    	for (int i = 2; i < tlen - 2; i++) {
    		int i_mirror = C * 2 - i; // i' = C - (i - C)
    		P[i] = (R > i) ? MIN(R - i, P[i_mirror]) : 0;
    		while (T[i - P[i] - 1] == T[i + P[i] + 1])
    			P[i]++;
    		
    		if (i + P[i] > R) {
    			C = i;
    			R = i + P[i];
    		}
    
    		if (P[i] > max_len) {
    			center_idx = i;
    			max_len = P[i];
    		}
    	}
    
    	int lps_idx = (center_idx - max_len - 1) / 2;
    	s[lps_idx + max_len] = '\0';
    	return &s[lps_idx];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.