leetcode1147 段式回文

思路：

不断贪心地寻找最短公共前后缀即可。贪心法的正确性证明：https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition/solution/tan-xin-fa-zheng-que-xing-de-xiang-xi-zheng-ming-b/

实现：

 1 class Solution
 2 {
 3 public:
 4     int dfs(string t, int l, int r)
 5     {
 6         if (l >= r) return l == r;
 7         int m = l + r >> 1, p = r, len = 0; 
 8         bool flg = false;
 9         while (p > m)
10         {
11             if (t[p] == t[l])
12             {
13                 len = r - p + 1;
14                 if (t.substr(l, len) == t.substr(p, len))
15                 {
16                     flg = true; break;
17                 }
18             }
19             p--;
20         }
21         if (flg) return dfs(t, l + len, r - len) + 2;
22         else return 1;
23     }
24     int longestDecomposition(string text)
25     {
26         int n = text.length();
27         return dfs(text, 0, n - 1);
28     }
29 };