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

#include <bits/stdc++.h>
using namespace std;

typedef long double lld;
typedef long long ll;

#define fr(a, b, i) for (ll i = a; i < b; i++)
#define rfr(a, b, i) for (ll i = a; i >= b; i--)
#define rep(i, n) fr(0, n, i)
#define ff first
#define ss second
#define pb push_back
#define endl '\n'
#define inf LLONG_MAX
#define all(c) (c).begin(), (c).end()
const ll mod = 1000000007;

template <typename T>
void chmin(T &f, T s) { f = min(f, s); }
template <typename T>
void chmax(T &f, T s) { f = max(f, s); }
ll expo(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1; } return res; }
ll modinv(ll a, ll b) { return expo(a, b - 2, b); }
ll modadd(ll a, ll b, ll m) { return (a % m + b % m) % m; }
ll modmul(ll a, ll b, ll m) { return (a % m * b % m) % m; }
ll modsub(ll a, ll b, ll m) { return ((a % m - b % m) + m) % m; }
ll moddiv(ll a, ll b, ll m) { return modmul(a, modinv(b, m), m) % m; }

class StringHash {
public:
    vector<long long> ps1, ps2;
    long long Q1 = 271, Q2 = 277, M1 = 1000000007, M2 = 998244353;

    StringHash(string s) {
        ps1 = vector<long long>(s.size() + 1);
        ps2 = vector<long long>(s.size() + 1);
        for (int i = 1; i <= s.size(); i++) {
            long long c = s[i - 1] + 1;
            ps1[i] = ((Q1 * ps1[i - 1]) + c) % M1;
            ps2[i] = ((Q2 * ps2[i - 1]) + c) % M2;
        }
    }

    long long powxy(long long int x, long long int y, long long M) {
        if (y == 0) return 1;
        if (y % 2 == 1) return (x * powxy(x, y - 1, M)) % M;
        long long int t = powxy(x, y / 2, M);
        return (t * t) % M;
    }

    long long substrHash1(int firstIndex, int lastIndex) {
        long long rem = (powxy(Q1, lastIndex - firstIndex + 1, M1) * ps1[firstIndex]) % M1;
        return (ps1[lastIndex + 1] - rem + M1) % M1;
    }

    long long substrHash2(int firstIndex, int lastIndex) {
        long long rem = (powxy(Q2, lastIndex - firstIndex + 1, M2) * ps2[firstIndex]) % M2;
        return (ps2[lastIndex + 1] - rem + M2) % M2;
    }

    pair<long long, long long> substrHash(int firstIndex, int lastIndex) {
        return { substrHash1(firstIndex, lastIndex), substrHash2(firstIndex, lastIndex) };
    }
};

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.size();
        if (n == 0) return 0;

        vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 1));
        StringHash st(text);

        rfr(n - 1, 0, l) {
            ll r = n - l - 1;
            fr(1, (r - l + 1) / 2 + 1, len) {
                ll firstend = l + len - 1, secondstart = r - len + 1;
                if (secondstart < firstend) break;

                if (st.substrHash(l, firstend) == st.substrHash(secondstart, r)) {
                    chmax(dp[l][r], 2 + (secondstart - 1 >= firstend + 1 ? dp[firstend + 1][secondstart - 1] : 0));
                }
            }
        }
        
        return dp[0][n - 1];
    }
};

68000