[5] Longest Palindromic Substring(TBC)

雖然是一個很慢的解法但是不管呵
是自己寫出來的而且通過測資>///<
還是中等難度>///<
無論如何就是開心！！！

找最長的回文substring
Longest Palindromic Substring
int isPalindrome(char* s, int len)
{
    for (int i = 0; i<len/2;i++)
    {
        if (s[i] != s[len-1-i])
            return 0;
    }
    return len;
}

char* longestPalindrome(char* s) {
    if (s==NULL)
        return s;
    int len = strlen(s);
    int index = -1;
    int tarLen = 0;
    int i,j,tmp;

    for(i=0; i<len;i++)
    {
        int pre = 0;
        for(j=0;j<i; j++)
        {
            tmp = isPalindrome(s+j,i-j+1);
            if (pre > tmp)
                break;
         
            if (tmp > tarLen)
            {
                tarLen = tmp;
                index = j;
                break;
            }
            pre = tmp;          
        }
    }

    if (tarLen == 0 && index<0)
    {
        tarLen = 1;
        index = 0;
    }
    char *ret = malloc(sizeof(char)*(tarLen+1));
    strncpy(ret,s+index,tarLen);
    ret[tarLen] = 0;
    return ret;
}
明天天亮再看心情要不要去看別人的超高速解法XD
先放個TBC~~~ccc~~~~
see this : Manacher’s algorithm