Можно ли как-то обрезать начало массива результата Z функции

Есть функция поиска наибольшего вхождения через Z функцию. Как видим начало z массива не используется.

Код:

std::pair<lu, lu> calculateZFunction(std::vector<hu>* source, lu subStringSize) {

    std::vector<llu> z(source->size());
    std::pair<lu,lu> result = std::make_pair(0, 0);
    for (llu i = subStringSize, l=0, r=0; i < source->size(); i++) {
        if (r >= i) z[i] = std::min(z[i - l], r - i + 1);
        while (z[i] + i < source->size() && (*source)[z[i]] == (*source)[z[i] + i]) {
            z[i]++;
        }
        
        if (z[i] > result.second){
            result.first = i;
            result.second = z[i];
        }
        
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    
    if (result.first) result.first -= (subStringSize+1);

    return result;
}

Т.е. используем Z функцию от S2#S1, ответ ищем в массиве после #.
Теоретически часть массива до # можно вообще убрать, добавив смещение.
Вот и вопрос - как правильно сделать так, чтобы уменьшить размер массива z до размера S2
Просто заменить z[i] на z[i - subStringSize] приводит к неправильному результату (ну или я криворукий).
Можете подсказать, как это реализовать?


Ответы (0 шт):