2

Суть задачи заключается в следующем.

Входной файл имеет следующий вид:

Например:

Входной файл
10
aaaaaaaaab
aaaaaaaaba

Выходной файл
1

Во входном файле 3 строчки. В первой строке записано единственное число

  n (1 ≤ n ≤ 1 000 000).

Далее следуют две строки длиной n, состоящие исключительно из маленьких букв латинского алфавита.
Необходимо проверить, возможно ли привести первую строку ко второй путем циклического сдвига влево. В примере выше, это возможно. Понадобится циклически сдвинуть влево первую строку на 1 элемент. В выходной файл мы записываем кол-во элементов, которые понадобилось сдвинуть для получения результата. В данном примере в выходном файле будет 1. Если получить желаемый результат не получается, то в файл необходимо записать -1.

Ограничение есть только на время (3 секунды максимум), на память никаких ограничений нет.

Что я смог придумать: сдвигать на 1 элемент по циклу и проверять, получили ли мы правильный результат (сдвиг я осуществлял при помощи реверса строки). Алгоритм не оптимальный, проверку по времени не проходит.

Эта задача относится к теме рекуррентных соотношений, но я не догадался как их тут использовать. Помогите с алгоритмом, пожалуйста.

Вот еще примеры:

Входной файл
10
aaaaaaaaab
aaaaaaabaa

Выходной файл
2

////////////////////////////////////////////

Входной файл
7
aabaabc
baabaaa

Выходной файл
-1

2

1 ответ 1

6

Можно подсчитать автокорреляционную функцию последовательности. Далее одним пробегом найти, при какой величине сдвига автокорреляционная функция принимает значение, равное сумме квадратов чисел последовательности (помним, что char имеет численное представление, не забываем буквы преобразовать к int, чтобы не переполниться).

Если хотя бы в одной точке автокорреляционная функция принимает это значение (оно кстати будет максимумом этой функции), то одна последовательность является циклическим сдвигом другой, и величина необходимого сдвига как раз и будет тем k, в котором автокорреляция максимальна.

Прикинем сложность алгоритма. Автокорреляцию можно подсчитать с помощью быстрого дискретного преобразования Фурье (переворачиваем вторую последовательность, и затем считаем свёртку). Это займёт O(nlogn), затем один пробег: O(n), итого O(nlogn).

Второй вариант. Берём вторую строку s2, приписываем её саму к себе s2+s2, затем делаем поиск строки s1 в строке s2+s2, это можно сделать алгоритмом Кнута-Морриса-Пратта за O(n) (подсчётом префикс-функции, или подсчётом Z-функции), если найдётся вхождение, то ответ "да", и индекс вхождения это величина искомого циклического сдвига. Итоговая сложность O(n), думаю этот алгоритм асимптотически оптимален.

Далее реализация на c++. Если хотите подумать самостоятельно - не читайте код. Сделано всё, за исключением, возможно, мелких ошибок типа ввода/вывода (функции поиска точно протестированы, остальное не тестил).

Реализация асимптотики O(n), реализацию через преобразование Фурье лень делать, она сложнее и там кода больше :)

#include <string>
#include <vector>

template<class T>
std::vector<int> z_function(const T& str)
{
    int n = str.size();
    std::vector<int> answer(n, 0);
    int l, r;
    l = 0;
    r = 1;
    for (int i = 1; i < n; ++i)
    {
        if (i < r)
        {
            answer[i] = std::min(r - i, answer[i - l]);
        }
        while ( ( i + answer[i] < n ) && ( str[answer[i]] == str[i + answer[i]]) )
        {
            ++answer[i];
        }
        if ( i + answer[i] > r)
        {
            l = i;
            r = i + answer[i];
        }
    }
    return answer;
}

template<class T>
std::vector<int> search_kmp(const T& pattern, const T& text, const T& marker = T("#"))
{
    std::vector<int> zf = z_function(pattern + marker + text);
    int ps = pattern.size();
    int ts = text.size();
    std::vector<int> answer;
    answer.reserve(ts);
    for (int i = 0; i + ps - 1 < text.size(); ++i)
    {
        if (zf[i + ps + 1] == ps)
        {
            answer.push_back(i);
        }
    }
    return answer;
}

int main()
{
    int N;
    std::string str1, str2;
    std::cin >> N;
    std::cin >> str1;
    std::cin >> str2;
    std::string str(str2+str2);
    std::vector<int> mas = search_kmp(str1, str);
    if (!mas.empty())
    {
        std::cout << mas[0] << std::endl;
    }
    else
    {
        std::cout << -1 << std::endl;
    }
    return 0;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.