Реализация самой длинной общей подстроки с использованием суффиксного массива

я использую эта программа для вычисления массива суффиксов и самого длинного общего префикса.

Мне необходимо вычислить самую длинную общую подстроку между двумя строками.

Для этого я объединяю строки, A#B а затем использовать этот алгоритм.

У меня есть Суффикс Массив sa[] и LCP[] массив.

Самая длинная общая подстрока — это максимальное значение LCP[] массив.

Чтобы найти подстроку, единственным условием является то, что среди подстрок общей длины, ответ, встречающийся в строке B в первый раз.

Для этого я поддерживаю максимум LCP []. Если LCP[curr_index] == maxтогда я убедился, что left_index подстроки B меньше, чем предыдущее значение left_index,

Однако такой подход не дает правильного ответа. Где вина?

max=-1;
for(int i=1;i<strlen(S)-1;++i)
{
//checking that sa[i+1] occurs after s[i] or not
if(lcp[i] >= max && sa[i] < l1 && sa[i+1] >= l1+1 )
{
if( max == lcp[i] && sa[i+1] < left_index ) left_index=sa[i+1];

else if (lcp[i] > ma )
{
left_index=sa[i+1];
max=lcp[i];
}
}
//checking that sa[i+1] occurs after s[i] or not
else if (lcp[i] >= max && sa[i] >= l1+1 && sa[i+1] < l1 )
{
if( max == lcp[i] && sa[i] < left_index) left_index=sa[i];

else if (lcp[i]>ma)
{
left_index=sa[i];
max=lcp[i];
}
}
}

2

Решение

AFAIK, Эта проблема из соревнования по программированию, и обсуждать проблемы программирования в текущем конкурсе до того, как редакционные статьи не будут выпущены … Хотя я даю вам некоторые идеи, как я получил Неправильный ответ с суффиксным массивом. Тогда я использовал суффикс автомат что дает мне принято.

Суффиксный массив работает в O(nlog^2 n) в то время как Suffix Automaton работает в O(n), Поэтому мой совет: используйте суффикс Automaton, и вы обязательно получите Accepted.
И если вы можете код решение этой проблемы, Вы обязательно закодируете это.

Также найдено на форуме codchef, что:

Try this case
babaazzzzyy
badyybac
The suffix array will contain baa... (From 1st string ) , baba.. ( from first string ) , bac ( from second string ) , bad from second string .
So if you are examining consecutive entries of SA then you will find a match at "baba" and "bac" and find the index of "ba" as 7 in second string , even though its actually at index 1 also .
Its likely that you may output "yy" instead of "ba"

А также справиться с ограничением …первая самая длинная общая подстрока, найденная во второй строке, должна быть записана для вывода … было бы очень легко в случае суффиксного автомата. Удачи!

1

Другие решения

Других решений пока нет …

Похожие вопросы
Добавить ответ
Для оформления сообщений Вы можете использовать следующие тэги:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Нажимая кнопку «Отправить», я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности этого сайта.