In the Leetcode Longest Palindromic Substring problem solution in C programming Given a string s, return the longest palindromic substring in s.
Leetcode Longest Palindromic Substring problem solution in C programming
char * longestPalindrome(char * s){
int pLength = strlen(s) + 1 + strlen(s) + 2;
int pStr[pLength];
int p[pLength];
pStr[0] = '@';
pStr[pLength - 1] = '%';
for(int i = 1; i < pLength - 1; i++){
if(i % 2){
pStr[i] = '#';
}else{
pStr[i] = s[i/2 - 1];
}
}
int iCenter = 0, iRadius = 0, iMirror = 0 ,iRight = 0, palindromeIndexStart = 0, palindromeMax = 0;
for(int i = 1; i < pLength - 1; i++){
iRight = iCenter + iRadius;
iMirror = 2 * iCenter - i;
p[i] = 0;
if(i <= iRight){
if(p[iMirror] <= iRight - i){
p[i] = p[iMirror];
}else{
p[i] = iRight - i;
}
}
while(pStr[i + p[i] + 1] == pStr[i - p[i] - 1]){
p[i] += 1;
}
if((i + p[i]) > iRight){
iCenter = i;
iRadius = p[i];
}
if(p[i] > palindromeMax){
palindromeMax = p[i];
palindromeIndexStart = (i - p[i])/2;
}
}
char * retChar = (char *)alloca(palindromeMax + 1);
retChar[palindromeMax] = 0;
strncpy(retChar, s+palindromeIndexStart, palindromeMax);
return retChar;
}
Also read,
- Leetcode Longest Palindromic Substring problem solution in C++
- Leetcode Longest Palindromic Substring problem solution in Java
- Leetcode Longest Palindromic Substring problem solution in Python
- Leetcode Longest Palindromic Substring problem solution in C#