神犇题解：见题目讨论区曹鹏神犇的讲解。
跪烂。。倒地不起。。
对于每一个合法解，我们都可以将其唯一地分解成若干个“链”。所谓链是指由那些小于n/2的字符组成的，并且最后一个字符满足2*i>n的合法字符串。
所以我们定义两个东西：
1.g（x）表示长度为x的链的数量。
2.v（x）表示长度为x的合法字符串数量。
那么很显然，v（x）=g（1）*v（x-1）+.....+g（p）*v（x-p）
p是链长度上限，也就是logn
所以是一个O（m*logn）的复杂度。
原文：http://www.cnblogs.com/enigma-aw/p/6358321.html