E111. Решение задачи "сжатие строки" за O (N)

e-maxx algorithm оригинал: C/C++ #algorithm #emaxx #string

Static

Источник: e-maxx.ru/algo, страница PDF 349.

Дана строка S. Требуется найти такую строку T, что строка S получается многократным повторением T. Из всех возможных T нужно выбрать наименьшую по длине.

Эту задачу очень просто решить за O (N) с помощью префикс-функции. Итак, пусть массив P - префикс-функция строки S, которую можно вычислить за O (N). Теперь рассмотрим значение последнего элемента P: P[N-1]. Если N делится на (N - P[N-1]), то ответ существует, и это N - P[N-1] первых букв строки S. Если же не делится, то ответа не существует. Корректность этого метода легко понять. P[N-1] равно длине наидлиннейшего собственного суффикса строки S, совпадающего с префиксом S. Если ответ существует, то, очевидно, начальный кусок строки S длиной (N - P[N-1]) и будет ответом, и, следовательно, N будет делиться на (N - P[N-1]). Если же ответа не существует, то (N - P[N-1]) будет равно какому-то непонятному значению, на которое N делиться не будет (иначе бы ответ существовал).

Реализация

int n = (int) s.length();

vector<int> p (n);

// ... здесь вычисление префикс-функции ...

int l = n - p[n-1];

if (n % l == 0)

cout << s.substr (l);

else

cout << "No Solution";

C# решение

auto-draft, проверить перед отправкой

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int n = (int) s.length();
    List<int> p (n);
    // ... здесь вычисление префикс-функции ...
    int l = n - p[n-1];
    if (n % l == 0)
            Console.WriteLine( s.substr (l);
    else
            Console.WriteLine( "No Solution";
}

C++ решение

сопоставлено/оригинал

int n = (int) s.length();
vector<int> p (n);
// ... здесь вычисление префикс-функции ...
int l = n - p[n-1];
if (n % l == 0)
        cout << s.substr (l);
else
        cout << "No Solution";

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int n = (int) s.length();
    ArrayList<Integer> p (n);
    // ... здесь вычисление префикс-функции ...
    int l = n - p[n-1];
    if (n % l == 0)
            System.out.println( s.substr (l);
    else
            System.out.println( "No Solution";
}

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.