Суфмасс и Касаи

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Здравствуйте! Недавно пытался сдать простую задачу, в которой нужно было посчитать суфмасс для циклических сдвигов строки, а по нему — lcp. Код построения суфмасса почти идентичен размещенному на e-maxx.ru в соответствующей статье. Lcp строил алгоритмом Касаи, но длительное время получал WA. После того, как я посортил куски суфмасса, находящиеся в одном классе эквивалентности, по убыванию индекса (т.е. по возрастанию длины), решение внезапно получило AC. Позже, я встретил похожую задачу, и опять все повторилось, спас только этот грязный хак с сортировкой. Теперь очень захотелось разобраться, что же я делаю не так. Возможно, это спецэффект Касаи, о котором нигде не написано? Или я криво его пишу? В любом случае, вот мой код. Прошу помочь разобраться!

Комментарии (9)

Написать комментарий?

_dangerous_

12 лет назад, # |

для циклических сдвигов лцп не работает, вроде на тесте abab какая-то хрень

→ Ответить

PavelKunyavskiy

+19

Тут надо плясать от доказательства Кассаи. Оно использует факт, что если i раньше j, то i+1 раньше j+1. Для циклических сдвигов это неверно. Надо просто это проверять и если что сбрасывать накопленный результат. Это случится O(1) раз.

kb.

12 лет назад, # ^ |

← Rev. 2 →

Вот проблема как раз таки из-за того, что я плохо понимаю, почему Касаи (на википедии все-таки с одной "с") вообще работает. А вот обозначения i и j, это имеется ввиду как в коде, т.е. текущий суффикс и следующий в суфмассе? Видимо, делая сортировку по убыванию, я правильного порядка невольно и добивался?

Казалось бы они сами будут отсортированы по неубыванию, т.к. сортировка стабильная. Так что странно.

Под i,j имеются ввиду два соседних суффикса в суфмассиве. Там случается проблема с последним, и она есть в любом случае для циклических сдвигов.

Однако код без магических строчек

int lstPos = 0;
for (int i = 0; i <= n; i++)
	if (i == n || c[p[i]] != c[p[i - 1]])
	{
		sort(p + lstPos, p + i, greater<int>());
		lstPos = i;
	}

получает WA на двух разных джаджах по двум разным задачам, а с ними — AC

А. По убыванию. Ну да. Это что-то меняет. Хотя, почему все становится хорошо, мне все равно не понятно.

можете не заморачиваться (хотя разобраться всегда интересно), если вам надо находить lcp для двух циклических сдвигов, можно сделать так: построить суффмассив на строке s+s+#, посчитать лсп, и когда надо найти лсп двух сдвигов — просто взять минимум на отрезке массива lcp

Ну хотелось бы иметь нормальный массив lcp все-таки, и ведь по сути это тоже хак, ни чем не лучше предложенного мной

ну да, ну просто ваш хак я не понимаю) почему он работает

Блог пользователя kb.