[C] 나비배열 찾기 (Palindrome)

char * longestPalindrome(char * s)
{
    int liLgstL = 1; // length of longest palindromic substring
    int liLgstS = 0; // start index of longest palindromic substring
    int liLgstE = 0; // end index of longest palindromic substring
    
    int liSLen = strlen(s);

    /* if length of palindromic substring is even number
       then there should be at least one couple of same character 
     */
    for(int i=0; i<liSLen; i++)
    {
        int iSt = i; /* start */
        int iEd = i; /* end   */
        
        /* Check same following characters */
        while( s[i] == s[i+1] && i+1 < liSLen )
        {
            i++;
            iEd++;
        }
        
        /* Check palindromic using iSt and iEd */
        while( iSt-1 >= 0 && iEd+1 < liSLen )
        {
            if( s[iSt-1] == s[iEd+1] )
            {
                iSt--;
                iEd++;
            }
        }
        
        /* Compare longer */
        if( iEd - iSt +1 > liLgstL )
        {
            liLgstL = iEd - iSt +1;
            liLgstS = iSt;
            liLgstE = iEd;
        }
    }
    
    char *lsRslt = malloc(liLgstL + 1);
    memcpy(lsRslt, &s[liLgstS], liLgstL);
    lsRslt[liLgstL] = 0x00;
    
    return lsRslt;
}

 

입력값에서 순서대로 읽어도, 거꾸로 읽어도 동일한 가장 긴 문자열을 찾는 함수. 

개인적으로는 나비가 날개를 펼치는 데칼코마니 형상이 생각나서 나비배열이라고 제목을 지었다.

동일한 문자열이 나오는 경우 계속해서 확장해가다가, 동일한 문자열이 나오지 않으면, 시작과 끝을 나비처럼 펼처서 Palindrome 문자를 찾는다.

 

깃허브 주소:

https://github.com/binary-river/algorithms/blob/Master/longestPalindrome_v2.c

GitHub - binary-river/algorithms: algorithms practices