<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 {
    void kmpVec(string text,vector<int> &vec) {
        int n = text.size();
        
        int len = 0;
        int i = 1;

        while(i < n) {
            if(text[i] == text[len]) {
                len++;
                vec[i] = len;
                i++;
            }
            else {
                if(len != 0) len = vec[len-1];
                else i++;
            }
        }
    }

    int solve(int start,int end,string text,vector<vector<int>> &dp) {
        if(dp[start][end] != -1) return dp[start][end];

        // if(end-start+1 == 1) return 1; 

        int n = text.size();
        vector<int> vec(n,0);
        kmpVec(text,vec);

        if(vec.back() == 0) return 1;
        
        int ans = 0;

        int ind = vec.back();
        while(ind != 0) {
            if(n-2*ind > 0) {
                int curr = 2 + solve(start+ind,end-ind,text.substr(ind,n-2*ind),dp);
                ans = max(ans,curr);
            }
            else if(n-2*ind == 0) {
                ans = max(ans,2);
            }
            ind = vec[ind-1];
        }

        return dp[start][end] = ans;
    }
public:
    int longestDecomposition(string text) {
        int n = text.size();
        vector<vector<int>> dp(n+1,vector<int>(n+1,-1));
        return solve(0,n-1,text,dp);
    }
};
82756