<p>You are given a string <code>text</code>. You should split it to k substrings <code>(subtext<sub>1</sub>, subtext<sub>2</sub>, ..., subtext<sub>k</sub>)</code> such that:</p>

<ul>
	<li><code>subtext<sub>i</sub></code> is a <strong>non-empty</strong> string.</li>
	<li>The concatenation of all the substrings is equal to <code>text</code> (i.e., <code>subtext<sub>1</sub> + subtext<sub>2</sub> + ... + subtext<sub>k</sub> == text</code>).</li>
	<li><code>subtext<sub>i</sub> == subtext<sub>k - i + 1</sub></code> for all valid values of <code>i</code> (i.e., <code>1 &lt;= i &lt;= k</code>).</li>
</ul>

<p>Return the largest possible value of <code>k</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;ghiabcdefhelloadamhelloabcdefghi&quot;
<strong>Output:</strong> 7
<strong>Explanation:</strong> We can split the string on &quot;(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;merchant&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can split the string on &quot;(merchant)&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;antaprezatepzapreanta&quot;
<strong>Output:</strong> 11
<strong>Explanation:</strong> We can split the string on &quot;(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text.length &lt;= 1000</code></li>
	<li><code>text</code> consists only of lowercase English characters.</li>
</ul>

class Solution {
public:
    int n;
    int solve(string& s, int i, vector<vector<int>>& tab, vector<int>& dp) {
        int j = n-i-1;
        if (i > j) return 0;
        if (dp[i] != -1) return dp[i];
        int ans = 1;
        for (int k = 1; k <= (j-i+1)/2; k++) {
            if (tab[i][j-k+1] >= k) {
                ans = max(ans, 2+solve(s, i+k, tab, dp));
            }
        }
        dp[i] = ans;
        return ans;
    }

    int longestDecomposition(string s) {
        n = s.size();
        vector<vector<int>> tab(n+1, vector<int>(n+1));
        for (int i = 0; i <= n; i++) {
            tab[i][n] = 0;
            tab[n][i] = 0;
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j>=0; j--) {
                tab[i][j] = 0;
                if (s[i] == s[j]) {
                    tab[i][j] = 1 + tab[i+1][j+1];
                }
            }
        }

        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < n; j++) {
        //         cout << tab[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        vector<int> dp(n, -1);
        
        return solve(s, 0, tab, dp);

        // for (int l = 1; l < n; l++) {
        //     for (int i = 0; i <= n-l; i++) {
        //         int j = i+l;

        //     }
        // }
    }
};
29634