[字符串] 最长回声子字符串（动态编程算法） ★ - I. 回声字符串、子字符串、后续字符串

---

" 回文串 ( Palindrome ) " 是 正反都一样的字符串 , abccba , 001100 等字符串 ;

给定一个字符串 " abcd " ,

" 子串 ( SubString ) "是连续取的子字符串 , 如 : “ab” , “bc” , “cd” , “bcd” 等 , 不能跳跃字符 ; ( 连续字符 )

$n$ 个字符串的子串个数是 $\frac{n(n+1)}{2}+1$ 个 ;

" 子序列 ( SubSequence ) " 是可以非连续取字符串中的字符 , 前后顺序不允许颠倒 , 如 “ad” , “bd” , “acd” 等 ; ( 非连续字符 )

$n$ 个字符串的子串个数是 $2^n$ 个 ( 集合的子集数 ) ;

验证一个字符串是否是回文串 , 最坏的情况下需要遍历 $\frac{n}{2}$ 次 ;

因此最暴力的方法验证回文子串 , 就是验证 $\frac{n(n+1)}{2}+1$ 个子字符串是否是回文串 , 每次都要遍历 $\frac{n}{2}$ 次 ;
暴力算法的时间复杂度是 $O(n^3)$ ;