字符串中最长不重复子串和最长回文子串算法

一） 这里用GOLANG实现了一个查找最长不重复子串的算法，在暴力查询的基础上作了优化，虽然速度还是比较慢，但是有助于理解后边高级的算法，值得一记。

暴力查询的优化思路：

1）如果我们已经查找到的最大子串长度比剩下没有for到的子串还长，那最大子串不可能会在发生改变了，我们就不往下找了，返回这个最大子串长度；

2）这个是最重要的：在我们发现某一个字符在子串中重复时，比如" abcdccefgd"中， i = 0, 在j = 4的时候会发现 4位上的字符'c'和前面位置2上的'c'重复。此时，我们不是i++了，而是 把i 挪到位置2后面的3上，从那里开始找子串。如果我们不这么做，而是继续i++， i = 1 和 i = 2 这两个也会在j=4处发现重复，从这里退出，最大不重复子串也仍然是i = 0时得到的那个数。

这个算法还可以优化，可以考虑提前分配一个数组来记录该把 i挪到哪里，而不是用函数调用的方法，往下看。

func lengthOfLongestSubstring(s string) int {
    sLen := len(s)   
    var maxSubLen, lastPos int
    
    for i := 0; i < sLen - 1; i++ {
        //第二个for,如果剩下的字符串长度都没有已经找到的maxSubLen长，那我们就可以不去找了
        if maxSubLen < sLen-i {
            for j := i+1; (j < sLen) ; j++ {
                lastPos = findCharInSubStringPosition(s[i:], j-i)
                if lastPos < 0 { 
            //j位置上的字符没有在s[i:j]中重复,可以测试一下是否要更新maxSubLen
                    if j-i > maxSubLen {
                        maxSubLen = j-i
                    }                
                } else { 
                // j 位置上的字符在s[i:j]中重复,重复位置为i+lastPos，i就从i+lastPos后一位开始
                // 因为若从i+1开始，那么后面还是会在到达目前的j位置时，出现与i+lastPos重复的情况，
                   
                    i = lastPos + i 
                    //这里我们把i挪到重复字符的第一个字符上，for结尾的i++帮我们挪到下一位
                    
                    break
                }
            }   
        
        }
        
    }
    
    if sLen != 0 {
        maxSubLen++ //计算过程中，都是用下标计算而已，真正的总数我们需要++一下
    }
    
    return maxSubLen
}

// 这个函数可以找到位置j处字符在 参数s中的位置，如果不存在，则返回-1
func findCharInSubStringPosition(s string, j int) int {
    for i := 0; i < j; i++ {
        if s[i] == s[j] {
            return i
        }           
    }
    
    return -1
}
           

借助外部的一个哈希表来保存一些东西：

func lengthOfLongestSubstring(s string) int {
  //只支持ASCII码，
    tmp := [128]int{}
    var start, maxSubstr, i int
    sLen := len(s)
    // nil string return 0
    if sLen == 0 {
        return 0
    }
    // initial hash tbl
    for i := 0; i < len(tmp); i++ {
        tmp[i] = -1
    }     
    
    for i = 0; i < sLen; i++ {
        if tmp[ s[i] ] >= start {
            if s[i] != s[start] && i - tmp[s[i]] > maxSubstr {
                maxSubstr = i - tmp[s[i]]
            }      
            
            start = tmp[ s[i] ] + 1            
        }
        
        if i - start > maxSubstr {
            maxSubstr = i - start 
        }
        
        tmp[ s[i] ] = i
    }
    
    //the last i++ isn't what we want
    i--
    if i - start > maxSubstr {
        maxSubstr = i - start
    }
    
    return maxSubstr + 1
}
           

二）最长回文子串算法

最长回文子串，首先用暴力搜索。接着进行改进，改进的是从母字符串往后面扫描，同时进行了优化，LeetCode上速度还行：

//最长回文子串 1
func longestPalindrome(s string) string {
	var subLen, maxLen, pos int
	var i, j int
	sLen := len(s)
	for i = 0; i < sLen; i++ {
		for j = i+1; j <= sLen; j++ {
			subLen = isPalindrome(s[i:j])
			if ( subLen > 0) &&  subLen > maxLen {
				maxLen = subLen
				pos = i
			}
		}
	}

	return s[pos: pos+maxLen]
}

func isPalindrome(s string) int {
	sLen := len(s)
	for i := 0; i < sLen/2; i++ {
		if s[i] != s[sLen - 1 -i] {
			return -1
		}
	}

	return sLen
}
//最长回文子串2
func longestPalindrome(s string) string {
	var tmpLen, maxLen, pos int
	var i, j int
	sLen := len(s)
	if sLen == 0 {
		return ""
	}

	for i = 0; i < sLen; i++ {
		if (sLen-i)*2 <= maxLen {
			break
		}
		for j = i; j >= 0 && 2*i-j < sLen; j-- {
			if s[j] != s[2*i-j] {
				break
			}
		}
		j++
		tmpLen = 2*(i-j) + 1
		if tmpLen > maxLen {
			maxLen = tmpLen
			pos = j
		}
		for j = 0; j <= i && i+j+1 < sLen; j++ {
			if s[i-j] != s[i+j+1] {
				break
			}
		}
		if j != 0 {
			j--
			tmpLen = 2 * (j+1)
			if tmpLen > maxLen {
				maxLen = tmpLen
				pos = i-j
			}
		}

	}

	return s[pos: pos+maxLen]
}