Z-функция

Дана строка s. Нужно вычислить Z-функцию s - для каждого i от 1 до |s|.

Z[i]=max{j: 0 <= j <= |s| - i + 1, s[1..j] = s[i..i + j -1]}.

В единственной строке входа - строка s длиной не более 1 000 000 символов, состоящая из маленьких латинских букв.
В выходной файл выводится для каждого i от 1 до |s| число Z[i]. Числа разделены пробелами.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::max;

inline int LongestCommonPrefix(const string& input_string,
                       int first_start,
                       int second_start) {
  int index = 0;
  while (max(first_start + index, second_start + index) < input_string.size() &&
         input_string[first_start + index] ==
           input_string[second_start + index]) {
    ++index;
  }
  return index;
}

void ZFunction(const string& input_string, vector<int>& result_values) {
  result_values.resize(input_string.size());
  result_values[0] = input_string.size();
  int left_index = 0;
  int right_index = 0;
  int index;
  for (int current_index = 1; current_index < input_string.size();
       ++current_index) {
    if (current_index > right_index) {
      index = LongestCommonPrefix(input_string, 0, current_index);
      result_values[current_index] = index;
      left_index = current_index;
      right_index = current_index + index - 1;
    } else if (result_values[current_index - left_index] <
               right_index - current_index + 1) {
      result_values[current_index] = result_values[current_index - left_index];
    } else {
      index = LongestCommonPrefix(input_string, right_index + 1,
                                 right_index - current_index + 1) + 1;
      result_values[current_index] = right_index - current_index + index;
      left_index = current_index;
      right_index = right_index + index - 1;
    }
  }
}

void WriteOutput(const vector<int>& vec) {
  for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;
}

int main() {
  string input_string;
  vector<int> z_function_values;
  cin >> input_string;
  ZFunction(input_string, z_function_values);
  WriteOutput(z_function_values);
  return 0;
}