Лексикографически минимальное вращение струны - PullRequest
2 голосов
/ 28 февраля 2020

Привет, поэтому я в основном пытаюсь понять этот кусок кода в отношении определения лексикографически минимального вращения строки, но я просто не могу понять, почему это работает. Я понимаю, что делают первые два if, но третий, когда есть новый минимум, принимает максимум от p до m+l+1. У кого-нибудь есть объяснение?

int p = 0, l = 0, m = 0, n = 0;
string inp;

cin >> inp;
n = inp.size();
p = l = 1;

while (p < n && m + l + 1 < n) {
  if (inp[m + l] == inp[(p + l) % n])
    ++l;

  if (inp[m + l] < inp[(p + l) % n])
    p += l + 1, l = 0;

  if (inp[m + l] > inp[(p + l) % n]) {
    if (m + l + 1 < p) m = p;
    else m = m + l + 1;

    p = m + 1;
    l = 0;
  }
}

cout << m;
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...