<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:
    const long long MOD = 1e9 + 7;

    int longestDecomposition(string text) {
        int n = text.size();

        vector<int> dp((n-1)/2 + 1, 1);
        long long p = 53;
        long long pow[1001];
        pow[0] = 1; for(int i = 1; i<1001; i++) {pow[i] = pow[i-1] * p; pow[i]%=MOD;}
        //dp[i] // for string i...n-1-i whats the maximum k
        // 0 1 2 3 4 5 6
        for(int i = (n-1)/2; i>=0; i--){
            //fill for 
            //lps[i] gives maximum prefix that is also a suffix
            long long hashFront = 0, hashBack = 0; 
            int j = n - 1 - i;
            for(int l = 1; i + l - 1 <= (n-1)/2; l++){
                hashFront*=p;
                hashFront += (text[i + l - 1] - 'a' + 1);
                hashFront%=MOD;
                hashBack += (text[j - l + 1] - 'a' + 1)*pow[l - 1];
                hashBack%=MOD;

                if(hashBack == hashFront && 
                   text.substr(i, l) == text.substr(j-l+1, l)){
                    int count = 1 + (i!=j);
                    count +=(i + l <= (n-1)/2 ? dp[i + l] : 0);
                    dp[i] = max(dp[i], count);
                }
            }
        }

        return dp[0];
    }
};
50293