Вопрос по построению суффиксного массива

Правка ru1, от Azret, 2016-04-01 08:15:54

Здравствуйте.

Читаю статью с e-maxx. Вот кусок кода:

	for (int i=0; i<n; ++i) {
		pn[i] = p[i] - (1<<h);
		if (pn[i] < 0)  pn[i] += n;
	}
	memset (cnt, 0, classes * sizeof(int));
	for (int i=0; i<n; ++i)
		++cnt[c[pn[i]]];
	for (int i=1; i<classes; ++i)
		cnt[i] += cnt[i-1];
	for (int i=n-1; i>=0; --i)
		p[--cnt[c[pn[i]]]] = pn[i];

Почему в p[] будет содержаться перестановка для циклических сдвигов длины 2k после этой сортировки? Мы же просто отсортили вторые половинки..

Теги суффиксный, массив, вопрос, построение

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Azret 2016-04-01 09:55:55 585 Initial revision for English translation
ru2 Русский Azret 2016-04-01 08:17:33 40
ru1 Русский Azret 2016-04-01 08:15:54 551 Первая редакция (опубликовано)