Факторизація Ліндона

Факторизація Ліндона

Спершу означимо поняття факторизації Ліндона.

Рядок називається простим (або словом Ліндона), якщо він строго менший за будь-який зі своїх нетривіальних суфіксів. Приклади простих рядків: $a$, $b$, $ab$, $aab$, $abb$, $ababb$, $abcd$. Можна показати, що рядок є простим тоді й лише тоді, коли він строго менший за всі свої нетривіальні циклічні зсуви.

Далі нехай задано рядок $s$. Факторизація Ліндона рядка $s$ — це розклад $s = w_1 w_2 \dots w_k$, де всі рядки $w_i$ прості й розташовані в незростаючому порядку $w_1 \ge w_2 \ge \dots \ge w_k$.

Можна показати, що для будь-якого рядка така факторизація існує і є єдиною.

Коли підходить цей алгоритм?

• Потрібна факторизація Ліндона рядка або найменший циклічний зсув за $O(n)$ і $O(1)$ пам'яті?
• Задача саме про слова Ліндона / циклічні зсуви, а не про загальний лексикографічний порядок суфіксів? (якщо потрібен порядок усіх суфіксів → Суфіксний масив)
• Не потрібні запити про входження чи підрядки, лише жадібний прохід по рядку? (якщо потрібні підрядкові запити → Суфіксний автомат)

Алгоритм Дюваля

Алгоритм Дюваля будує факторизацію Ліндона за час $O(n)$, використовуючи $O(1)$ додаткової пам'яті.

Спершу введемо ще одне поняття: рядок $t$ називається передпростим, якщо він має вигляд $t = w w \dots w \overline{w}$, де $w$ — простий рядок, а $\overline{w}$ — префікс $w$ (можливо, порожній). Простий рядок також є передпростим.

Алгоритм Дюваля жадібний. У будь-який момент його виконання рядок $s$ фактично поділений на три рядки $s = s_1 s_2 s_3$, де факторизація Ліндона для $s_1$ вже знайдена та зафіксована, рядок $s_2$ є передпростим (і ми знаємо довжину простого рядка в ньому), а $s_3$ зовсім не зачеплений. На кожній ітерації алгоритм Дюваля бере перший символ рядка $s_3$ і намагається дописати його до рядка $s_2$. Якщо $s_2$ перестає бути передпростим, то факторизація Ліндона для деякої частини $s_2$ стає відомою, і ця частина переходить до $s_1$.

Опишемо алгоритм детальніше. Вказівник $i$ завжди вказуватиме на початок рядка $s_2$. Зовнішній цикл виконуватиметься, доки $i < n$. Усередині циклу ми використовуємо два додаткові вказівники: $j$, який вказує на початок $s_3$, і $k$, який вказує на поточний символ, з яким ми зараз порівнюємо. Ми хочемо додати символ $s[j]$ до рядка $s_2$, що вимагає порівняння із символом $s[k]$. Можливі три різні випадки:

• $s[j] = s[k]$: якщо це так, то додавання символу $s[j]$ до $s_2$ не порушує його передпростоти. Тож ми просто збільшуємо вказівники $j$ і $k$.
• $s[j] > s[k]$: тут рядок $s_2 + s[j]$ стає простим. Ми можемо збільшити $j$ і скинути $k$ назад на початок $s_2$, щоб наступний символ можна було порівняти з початком простого слова.
• $s[j] < s[k]$: рядок $s_2 + s[j]$ більше не є передпростим. Тому ми розіб'ємо передпростий рядок $s_2$ на його прості рядки та залишок, можливо порожній. Простий рядок матиме довжину $j - k$. На наступній ітерації ми починаємо знову з рештою $s_2$.

Реалізація

Тут ми наводимо реалізацію алгоритму Дюваля, яка повертає шукану факторизацію Ліндона заданого рядка $s$.

C++

vector<string> duval(string const& s) {
    int n = s.size();
    int i = 0;
    vector<string> factorization;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k) {
            factorization.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return factorization;
}

Python

def duval(s: str) -> list[str]:
    n = len(s)
    i = 0
    factorization = []
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i  # знайдено новий менший символ — починаємо просте слово заново
            else:
                k += 1  # символ повторюється — рухаємось далі
            j += 1
        # довжина простого слова дорівнює j - k; виокремлюємо всі його копії
        while i <= k:
            factorization.append(s[i:i + (j - k)])
            i += j - k
    return factorization

TypeScript

function duval(s: string): string[] {
  const n = s.length;
  let i = 0;
  const factorization: string[] = [];
  while (i < n) {
    let j = i + 1;
    let k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j]) {
        k = i; // знайдено новий менший символ — починаємо просте слово заново
      } else {
        k++; // символ повторюється — рухаємось далі
      }
      j++;
    }
    // довжина простого слова дорівнює j - k; виокремлюємо всі його копії
    while (i <= k) {
      factorization.push(s.substring(i, i + (j - k)));
      i += j - k;
    }
  }
  return factorization;
}

Go

func duval(s string) []string {
    n := len(s)
    i := 0
    var factorization []string
    for i < n {
        j, k := i+1, i
        for j < n && s[k] <= s[j] {
            if s[k] < s[j] {
                k = i // знайдено новий менший символ — починаємо просте слово заново
            } else {
                k++ // символ повторюється — рухаємось далі
            }
            j++
        }
        // довжина простого слова дорівнює j - k; виокремлюємо всі його копії
        for i <= k {
            factorization = append(factorization, s[i:i+(j-k)])
            i += j - k
        }
    }
    return factorization
}

Складність

Оцінімо час роботи цього алгоритму.

Зовнішній цикл while виконує не більше ніж $n$ ітерацій, оскільки наприкінці кожної ітерації $i$ збільшується. Другий внутрішній цикл while також працює за $O(n)$, оскільки він лише виводить підсумкову факторизацію.

Тож нас цікавить лише перший внутрішній цикл while. Скільки ітерацій він виконує в найгіршому випадку? Легко бачити, що прості слова, які ми визначаємо на кожній ітерації зовнішнього циклу, довші за залишок, який ми додатково порівнювали. Тому й сума залишків буде меншою за $n$, а це означає, що ми виконуємо щонайбільше $O(n)$ ітерацій першого внутрішнього циклу while. Насправді загальна кількість порівнянь символів не перевищить $4n - 3$.

Знаходження найменшого циклічного зсуву

Нехай задано рядок $s$. Ми будуємо факторизацію Ліндона для рядка $s + s$ (за час $O(n)$). Ми шукатимемо в цій факторизації простий рядок, який починається в позиції, меншій за $n$ (тобто починається в першому входженні $s$), і закінчується в позиції, більшій або рівній $n$ (тобто в другому входженні $s$). Стверджується, що позиція початку цього простого рядка буде початком шуканого найменшого циклічного зсуву. Це легко перевірити, скориставшись означенням розкладу Ліндона.

Початок простого блоку можна легко знайти — достатньо запам'ятати вказівник $i$ на початку кожної ітерації зовнішнього циклу, який позначав початок поточного передпростого рядка.

Отже, отримуємо таку реалізацію:

C++

string min_cyclic_string(string s) {
    s += s;
    int n = s.size();
    int i = 0, ans = 0;
    while (i < n / 2) {
        ans = i;
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k)
            i += j - k;
    }
    return s.substr(ans, n / 2);
}

Python

def min_cyclic_string(s: str) -> str:
    s += s  # подвоюємо рядок, щоб охопити всі циклічні зсуви
    n = len(s)
    i, ans = 0, 0
    while i < n // 2:
        ans = i  # запам'ятовуємо початок поточного передпростого рядка
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            i += j - k
    return s[ans:ans + n // 2]

TypeScript

function minCyclicString(s: string): string {
  s += s; // подвоюємо рядок, щоб охопити всі циклічні зсуви
  const n = s.length;
  let i = 0;
  let ans = 0;
  while (i < Math.floor(n / 2)) {
    ans = i; // запам'ятовуємо початок поточного передпростого рядка
    let j = i + 1;
    let k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j]) {
        k = i;
      } else {
        k++;
      }
      j++;
    }
    while (i <= k) {
      i += j - k;
    }
  }
  return s.substring(ans, ans + Math.floor(n / 2));
}

Go

func minCyclicString(s string) string {
    s += s // подвоюємо рядок, щоб охопити всі циклічні зсуви
    n := len(s)
    i, ans := 0, 0
    for i < n/2 {
        ans = i // запам'ятовуємо початок поточного передпростого рядка
        j, k := i+1, i
        for j < n && s[k] <= s[j] {
            if s[k] < s[j] {
                k = i
            } else {
                k++
            }
            j++
        }
        for i <= k {
            i += j - k
        }
    }
    return s[ans : ans+n/2]
}

Задачі

• UVA #719 - Glass Beads