Подскажите как решить задачу с помощью z-функции на c++

Алгоритм должен проходить временные рамки, как я думаю он должен работать, не медленее чем O(nlogn). Мне достаточно идеи решения, не обязательно писать код.

Код, который я написал до текущего момента по идеи, которая в корне неверна:

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    vector<int> z(s.size(), 0);
    int l = 0, r = 0;
    for (auto i = 1; i < z.size(); i++)
    {
        if (r >= i)
        {
            z[i] = min(z[i - l], r - i + 1);
        }
        while (z[i] + i < s.size() && s[z[i]] == s[z[i] + i])
        {
            z[i]++;
        }
        if (i + z[i] - 1 > r)
        {
            l = i;
            r = i + z[i] - 1;
        }
    }

    int indexBorder = 0;
    for (auto i = 1; i < z.size(); i++)
    {
        if (i + z[i] == s.size())
        {
            indexBorder = i;
        }
    }

    int c = 0;
    if (indexBorder != 0) // если есть грань
    {
        vector<bool> isHigher(indexBorder, false);
        for (auto i = 1; i < indexBorder; i++)
        {
            int j;
            if (z[i] == 0)
            {
                j = 0;
            } else
            {
                j = z[i];
            }

            while (s[j] < s[j + i] && j < indexBorder)
            {
                j++;
            }
            if (j != indexBorder)
            {
                c++;
                isHigher[j] = true;
            }
        }

        for (auto i = 1; i < z[indexBorder]; i++)
        {
            if (isHigher[i])
            {
                c++;
            }
        }

        int j = 0;
        while (s[j] < s[j + z[indexBorder]] && j + z[indexBorder] < indexBorder)
        {
            j++;
        }
        if (j + z[indexBorder] != indexBorder)
        {
            c++;
        }
    } else // если нет, пересчитываем все строки
    {
        for (auto i = 1; i < s.size(); i++)
        {
            int j = 0;
            while (s[j] < s[j + i] && j < s.size() - 1)
            {
                j++;
            }
            if (j != s.size() - 1)
            {
                c++;
            }
        }
    }

    cout << c + 1;
}