0

Я сделал программу, она работает как задумано, но она не проходит тесты на сайте, только 3/10(https://tutor.amcbridge.com/#/Projects/491bca5d-fc13-8261-DCD0-D68C1280FF43). Скорее всего, я что-то упустил или неправильно понял условие. На всех тестовых случаях, которые я придумал, это работает так, как и должно. Можете ли вы помочь найти случай, в котором он не работает. В программе использовался алгоритм Rabin-Carp и бинарный поиск

Описание

Предположим, что приведена последовательность целочисленных чисел с n -элементами. Массив целых чисел B с k<n -элементами называется повторным подмассивом последовательности A[0], …, A[n-1], если существуют как минимум два индекса i и j, 0 ≤ i < j ≤ n-k, такие, что оба подмассива {A[i], A[i+1], …, A[i+k-1]} и {A[j], A[j+1], …, A[j+k-1]} эквивалентны B. Например, последовательность {1 2 1 2 1} имеет повторяющиеся подпоследовательности: {1}, {2}, {1 2}, {2 1}, {1 2 1}.

Найдите самый длинный повторный подмассив.

Ввод

Члены последовательности, целые числа от 1 до 255.

Терминирующее число 0.

Вывод

Целое число, длина самого длинного повторного подмассив.

Пример

Ввод:

1 2 1 2 1 0

Output:

3

Код:

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

class Solution
{
    static void Main(string[] args)
    {
        string input = Console.ReadLine().Split('0')[0];    //take symbols before zero
        var numbers = input.Trim().Split(' ').Select(n => Int32.Parse(n)).ToList<int>();
        Console.Write(LongestDupSubstring(numbers).Count);
    }

    public static List<int> LongestDupSubstring(List<int> s)
    {
        var lds = new List<int>();
        var n = s.Count;

        var left = 1;
        var right = n;

        while (left <= right)
        { 
            var mid = left + (right - left) / 2;

            var dup = GetDup(mid, s);

            if (dup != null)
            {
                lds = dup;
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return lds;
    }

    private static List<int> GetDup(int mid, List<int> s)
    {
        var hash = Hash(s.Take(mid).ToList<int>());

        var set = new HashSet<long> { hash };

        var pow = 1L;

        for (var i = 1; i < mid; i++)
            pow *= 31;

        var n = s.Count;

        for (var i = 0; i < n - mid; ++i)
        { //O(n)
            hash = NextHash(pow, hash, s[i], s[i + mid]);

            if (!set.Add(hash))
                return s.Skip(i +1).Take(mid).ToList<int>();
        }

        return null;
    }

    private static long Hash(List<int> s)
    {
        var h = 0L;
        var a = 1L;

        var n = s.Count;

        for (var k = n; k >= 1; k--)
        {
            var ch = s[k - 1];
            h += (ch - 'a' + 1) * a;
            a *= 31;
        }

        return h;
    }

    private static long NextHash(long pow, long hash, int left, int right)
    {
        return (hash - (left - 'a' + 1) * pow) * 31 + (right - 'a' + 1);
    }
}
1
  • А зачем это в алгоритме? var mid = left + (right - left) / 2;?
    – tym32167
    14 июл 2022 в 13:44

1 ответ 1

0

Постройте суффиксный массив и посчитайте на нём LCP (длины наибольших общих префиксов соседних суффиксов). Самое большое значение в LCP - то, что нужно

Вторая задача описана по той же ссылке, или можно посмотреть алгоритм Касаи (на Python с примером применения здесь, на Java в вики )

Ваш ответ

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

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