<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 z[1000][1000];
void z_function(int ind,string s) {
    int n = s.size();
    int l = 0, r = 0;
    z[ind][0]=n;
    for(int i = 1; i < n; i++) {
        z[ind][i]=0;
        if(i < r) {
            z[ind][i] = min(r - i, z[ind][i - l]);
        }
        while(i + z[ind][i] < n && s[z[ind][i]] == s[i + z[ind][i]]) {
            z[ind][i]++;
        }
        if(i + z[ind][i] > r) {
            l = i;
            r = i + z[ind][i];
        }
    }
}
int dp[1000];
int f(int ind,string& s)
{
    int n=s.size();
    int cnt=(n-ind-1-ind+1);
    if (ind >= (n+1)/2) return 0;
    if (dp[ind]!=-1) return dp[ind];
    cnt/=2;
    int ans=1;
    int lst=n-ind-1;
    int curr=cnt;
    for (int j=lst-cnt+1;j<=lst;j++){
        if (z[ind][j-ind] >= curr){
            // cout<<ind<<" -> "<<j-ind<<" "<<z[ind][j-ind]<<"\n";
            // cout<<ind+curr<<"\n";
            ans=max(ans,2+f(ind+curr,s));
        }
        curr--;
    }
   // cout<<ind<<" "<<ans<<"\n";
    return dp[ind]=ans;
}
class Solution {
public:
    int longestDecomposition(string s) {
        int n=s.size();
        for (int i=0;i<n;i++){
            z_function(i,s.substr(i));
        }
       // cout<<z[0][0]<<" "<<z[0][1]<<" "<<z[1][0]<<"\n";
        memset(dp,-1,sizeof(dp));
        return f(0,s);
    }
};
20780