题意:

给定一个长度不超过1000的字符串,求它的回文子串串的数量mod10007。

分析:

我们知道如果求最长回文子串,我们可以做到O(n2)求解。如何做到的呢?如果用s[i]表示字符串第i位的字符,f(i,j)表示从i到j的子串中回文子串的最长长度,那么
$$
f(i,j)=max\begin{cases}
f(i+1,j)\\
f(i,j-1) \\
f(i+1,j-1) +1 & \text{(s[i]==s[j])}
\end{cases}
$$
我们发现求最长回文子串是分s[i]==s[j]与否进行转移的。
如果是求回文子串数呢?
经过思考,我们会发现,如果s[i]!=s[j],i,j之间的回文子串只有可能出现在s[i...j-1]或s[i+1...j]这两个区间中。由于这两个区间有重复部分[i+1...j-1],所以我们不妨像容斥原理那样将中间的减去。
如果s[i]==s[j]呢?i,j之间的回文子串又有了更多可能:除了s[i]!=s[j]的情况之外,还出现了s[i...j]区间中的,以及s[i]s[j]组成的回文串。所以我们可以列出状态转移方程:
$$
f(i,j)=max\begin{cases}
f(i+1,j) + f(i,j-1) - f(i+1,j-1) & \text{(s[i]!=s[j])} \\
f(i+1,j) + f(i,j-1) + 1& \text{(s[i]==s[j])}
\end{cases}
$$
所以我们就可以获得代码: