<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>

int calc(int i,int j,vector<vector<int>>&ans,vector<vector<int>>&lps){
    if(i>j)
    return 0;
    if(i==j)
    return 1;
    if(ans[i][j]!=-1)
    return ans[i][j];
    int val=1;
    int itr_i=i,itr_j=j;
    while(1){
        int cnt=lps[itr_i][itr_j];
        if(cnt==0)
        break;
        int temp=calc(i+cnt,j-cnt,ans,lps);
        if(temp!=-1)
        val=max(val,temp+2);
        itr_j=itr_i+cnt-1;
    }
    return ans[i][j]=val;
}
class Solution {
public:
    int longestDecomposition(string txt) {
        int n=txt.size();
        vector<vector<int>>lps(n,vector<int>(n,0));
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int k=lps[i][j-1];
                while(k && txt[i+k]!=txt[j]){
                    k=lps[i][i+k-1];
                    //cout<<11<<endl;
                }
                if(txt[i+k]==txt[j])
                k++;
                lps[i][j]=k;
                //cout<<i<<" "<<j<<" "<<lps[i][j]<<endl;
            }
        }
        //cout<<lps[3][28]<<endl;
        //cout<<11<<endl;
        vector<vector<int>>ans(n,vector<int>(n,-1));
        return calc(0,n-1,ans,lps);
    }
};
73903