leetcode专题——回文串问题
回文串问题
根据回文特性进行分析
具体问题具体分析，往往思路就是从这里来的。回文问题主要是判断回文的时间复杂度太高，可以考虑DP、哈希表、字典树、字符串哈希、KMP、马拉车等优化对回文的判断。
暴力解
有些问题可以先尝试，说不定能通过，但是形如O(n!)或者指数级复杂度就可以不考虑了。
DP
一般是子序列问题，迫不得已，没办法直接中心扩展。考虑类似LCS问题的区间DP思路
中心扩展算法
从某个位置向两侧扩展，避免暴力法枚举所有的子串。
字符串哈希
一般用于解决字符串是否相等的情况，找子串也比较有用，相当于预先存储了字符串。
字符串哈希，将字符串看作base进制的数，其对应的10进制值就是其哈希值，因为哈希值很容易超出范围，所以需要模一个很大的质数，一般来讲还是不容易哈希冲突的。一般来说，我们选取一个大于字符集大小（即字符串中可能出现的字符种类的数目）的质数作为base，再选取一个在字符串长度平方级别左右的质数作为 mod，产生哈希碰撞的概率就会很低。
马拉车
似乎很多问题都能用这个，但是我知难而退了。。。