<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 dp[1005];
    string s;
    int n,q;
    int p=998244353;
    vector<int>hash,pow;

    int rec(int i){
        if(i>=(n+1)/2)return 0;
        if(dp[i]!=-1)return dp[i];
        string x="",y="";
        int ans=1;
        for(int k=i;;k++){
            //i to k including 
            int st=n-k-1;
            if(n-k-1<=k)break;
            //hash1 i to k
            int hash1=((hash[k]-((i==0)?0:(1LL*hash[i-1]*pow[(k-i+1)]%p)))%p+p)%p;
            int hash2=((hash[n-i-1]-(1LL*hash[n-k-2]*pow[(n-i-1-(n-k-1)+1)])%p)%p+p)%p;
            if(hash1==hash2)ans=max(ans,2+rec(k+1));
        }
        return dp[i]=ans;
    }
    int longestDecomposition(string text) {
        s=text;
        n=s.length();
        memset(dp,-1,sizeof(dp));
        mt19937_64 rng(time(0));
        q=rng()%p;
        hash.resize(n);
        pow.resize(n);
        pow[0]=1;
        hash[0]=(s[0]-'a'+1);
        for(int i=1;i<n;i++){
            hash[i]=(1LL*hash[i-1]*q%p+(s[i]-'a'+1))%p;
            pow[i]=(1LL*pow[i-1]*q)%p;
        }
        // for(int i=0;i<n;i++)cout<<i<<' '<<rec(i)<<endl;;
        // cout<<endl;
        return rec(0);
    }
};
11926