Lexicographically minimal string rotation

Viewed 82

Hi so I'm basically trying to understand this piece of code in regards to determining the lexicographically minimal string rotation but I just can't seem to understand why it works. I understand what the first two ifs do but the third one, when there is a new minimum, it takes the maximum between p and m+l+1. Does anyone have an explanation?

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;
0 Answers
Related