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

#define ll long long int
ll mod = 1e9+7;
class Solution {
public:
   ll dp[1001][1001];
   ll p = 256;
   ll pre[1009];
   ll pow[1009];
   ll ok(ll l ,ll r){
     ll res = (pre[r]-(pre[l]*pow[r-l])%mod+mod)%mod;
     return res%mod;
   }
   ll solve(ll l , ll r, string &s ){
       if(r-l<-1){
         return -1e16;
       }
       else if(r-l==-1){
        return 0;
       }
       if(dp[l][r]!=-1){
        return dp[l][r];
       }
       ll ans = 1;
       for(int i = l;i<=r;i++){
           ll dis= (i-l+1);
           ll one,two;
           if(l-1>=0){
              one = ok(l-1,l+dis-1);
           }
           else{
            one = pre[l+dis-1];
           }
           if(r-dis>=0){
            two = ok(r-dis,r);
           }
           else{
            two = pre[r];
           }
           if(one==two){
               ll a= 2+solve(i+1,r-dis,s);
               ans = max(ans,a);
           }
       }
       return dp[l][r]= ans;
   }
    int longestDecomposition(string text) {
         string s = text;
         ll n = s.size();
         memset(dp,-1,sizeof(dp));
         pre[0]= s[0]-'a'+1;
         pow[0]=1;
         for(ll i = 1;i<n;i++){
             pre[i]=(pre[i-1]*p+s[i]-'a'+1)%mod;
             pow[i]= (pow[i-1])*p%mod;
         }
        return solve(0,n-1,s); 
    }
};
17829