<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 zf(int i, int j, string &s){
    vector<int> srep(s.length());
    int en = j;
    int l = i;
    int r = i+1;
    while(r<j+1){
        if(s[l] == s[r]){
            l++;
            srep[r] = l-i;
            
            r++;
        }else if(l!=i){
            l = srep[l-1] + i;
        }else{
            r++;
        }
    }
    // cout<<i<<" "<<j<<endl;
    // for(int i=0; i<srep.size(); i++){
    //     cout<<srep[i]<<" ";
    // }
    // cout<<endl;
    int ans = srep[j];
    if(ans == 0){
        return 0;
    }
    while(srep[i+ans-1] != 0){
        ans = srep[i+ans-1];
        if(ans==0){
            break;
        }
    }
    return ans;
}
class Solution {
public:
    int longestDecomposition(string text) {
        int l = 0; int r = text.length()-1;
        int count = 0;
        while(l<=r){
            if(l==r){
                count++;
                break;
            }
            int a = zf(l, r, text);
            // cout<<l<<" "<<r<<endl;
            cout<<text.substr(l, r-l+1)<<endl;
            // cout<<a<<" ";
            if(a==0){
                count++;
                break;
            }
            l+= a;
            r-= a;
            count+= 2;
        }
        // cout<<endl;
        return count;
    }
};
14878