Суффиксный массив - История изменений

Ctrlalt в 15:37, 11 апреля 2026

2026-04-11T15:37:04Z

@@ Строка 129: / Строка 129: @@
       return a.substr(from, len);
+  }
 == Ссылки ==

Ctrlalt: /* Ссылки */

2020-08-21T04:53:40Z

Ссылки

← Предыдущая версия		Версия от 04:53, 21 августа 2020
Строка 131:		Строка 131:

	== Ссылки ==		== Ссылки ==
	* [http://codeforces.com/edu/course/2/lesson/2 Codeforces — Суффиксный массив]		* [http://codeforces.com/edu/course/2/lesson/2 Codeforces EDU — Суффиксный массив]
	* [http://e-maxx.ru/algo/suffix_array e-maxx — Суффиксный массив]		* [http://e-maxx.ru/algo/suffix_array e-maxx — Суффиксный массив]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2 neerc.info.ru/wiki — Суффиксный массив]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2 neerc.info.ru/wiki — Суффиксный массив]

Ctrlalt: /* Ссылки */

2020-02-23T19:28:01Z

Ссылки

← Предыдущая версия		Версия от 19:28, 23 февраля 2020
Строка 135:		Строка 135:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2 neerc.info.ru/wiki — Суффиксный массив]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2 neerc.info.ru/wiki — Суффиксный массив]
	* [http://algorithmica.org/ru/suffix-array Algorithmica.org — Суффиксный массив]		* [http://algorithmica.org/ru/suffix-array Algorithmica.org — Суффиксный массив]
			* [http://um-nik.github.io/suffix-array Данилюк А. Суффиксный массив]
			* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/Suffix_Array_lecture_A.pdf Тихомиров М., Останин А. Лекция по суффиксному массиву]
	* [http://habr.com/ru/post/115346/ Habr — Суффиксный массив — удобная замена суффиксного дерева]		* [http://habr.com/ru/post/115346/ Habr — Суффиксный массив — удобная замена суффиксного дерева]
	* [http://visualgo.net/en/suffixarray VisuAlgo — Suffix Array]		* [http://visualgo.net/en/suffixarray VisuAlgo — Suffix Array]

Ctrlalt в 17:36, 23 февраля 2020

2020-02-23T17:36:44Z

@@ Строка 111: / Строка 111: @@
           res += (p.size() - 1 - p[i]) - lcp[i];
       return res;
+  }

Ctrlalt в 16:46, 23 февраля 2020

2020-02-23T16:46:06Z

← Предыдущая версия		Версия от 16:46, 23 февраля 2020
Строка 102:		Строка 102:
	}		}
	return lcp;		return lcp;
			}

			== Количество различных подстрок ==

			long long distinctSubstringsCount(const vector<int> &p, const vector<int> &lcp) {
			long long res = 0;
			for (int i = 1; i < p.size(); i++)
			res += (p.size() - 1 - p[i]) - lcp[i];
			return res;
	}		}

Ctrlalt в 16:38, 23 февраля 2020

2020-02-23T16:38:40Z

@@ Строка 84: / Строка 84: @@
   int count(const string &s, const vector<int> &p, const string &t) {
       return upperBound(s, p, t) - lowerBound(s, p, t);
+  }

Ctrlalt: /* Поиск подстрок */

2020-02-23T16:22:14Z

Поиск подстрок

← Предыдущая версия		Версия от 16:22, 23 февраля 2020
Строка 58:		Строка 58:
	== Поиск подстрок ==		== Поиск подстрок ==

	int ~~count~~(const string &s, const vector<int> &p, const string &t) {		int lowerBound(const string &s, const vector<int> &p, const string &t) {
	int l = 0, r = p.size();		int l = 0, r = p.size();
	while (l + 1 < r) {		while (l + 1 < r) {
Строка 67:		Строка 67:
	l = m;		l = m;
	}		}
	~~int lb =~~ r;		return r;
			}

	l = 0, r = p.size();		int upperBound(const string &s, const vector<int> &p, const string &t) {
			int l = 0, r = p.size();
	while (l + 1 < r) {		while (l + 1 < r) {
	int m = l + (r - l) / 2;		int m = l + (r - l) / 2;
Строка 77:		Строка 79:
	l = m;		l = m;
	}		}
	~~int ub =~~ r;		return r;
			}

	return ub - lb;		int count(const string &s, const vector<int> &p, const string &t) {
			return upperBound(s, p, t) - lowerBound(s, p, t);
	}		}

Ctrlalt в 17:51, 22 февраля 2020

2020-02-22T17:51:33Z

← Предыдущая версия		Версия от 17:51, 22 февраля 2020
Строка 29:		Строка 29:

	return p;		return p;
			}

	Построение за NlogN:		Построение за NlogN:

	Меняем вызов <tt>sort()</tt> на следующий фрагмент:		Меняем вызов <tt>sort()</tt> внутри цикла на следующий фрагмент:
	for (int i = 0; i < n; i++)		for (int i = 0; i < n; i++)
	p[i] = (p[i] - len + n) % n;		p[i] = (p[i] - len + n) % n;
Строка 53:		Строка 54:
	sortedP[rankFrom[rank[elem]]++] = elem;		sortedP[rankFrom[rank[elem]]++] = elem;
	p.swap(sortedP);		p.swap(sortedP);
			}

	== Поиск подстрок ==		== Поиск подстрок ==

Ctrlalt: Новая страница: «== Построение == Построение за Nlog²N: vector makeSuffixArray(string s) { s += '\0'; int n = s.size(); ve…»

2020-02-22T17:49:10Z

Новая страница: «== Построение == Построение за Nlog<sup>2</sup>N: vector<int> makeSuffixArray(string s) { s += '\0'; int n = s.size(); ve…»

Новая страница

== Построение ==

Построение за Nlog<sup>2</sup>N:
vector<int> makeSuffixArray(string s) {
s += '\0';
int n = s.size();

vector<int> p(n);
for (int i = 0; i < n; i++)
p[i] = i;
sort(p.begin(), p.end(), [&](int i, int j) { return s[i] < s[j]; });

vector<int> rank(n);
rank[p[0]] = 0;
for (int i = 1; i < n; i++)
rank[p[i]] = rank[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);

vector<pair<int, int>> rankPair(n);
for (int len = 1; len < n; len *= 2) {
for (int i = 0; i < n; i++)
rankPair[i] = { rank[i], rank[(i + len) % n] };

sort(p.begin(), p.end(), [&](int i, int j) { return rankPair[i] < rankPair[j]; });

rank[p[0]] = 0;
for (int i = 1; i < n; i++)
rank[p[i]] = rank[p[i - 1]] + (rankPair[p[i]] != rankPair[p[i - 1]]);
}

return p;

Построение за NlogN:

Меняем вызов <tt>sort()</tt> на следующий фрагмент:
for (int i = 0; i < n; i++)
p[i] = (p[i] - len + n) % n;
countSort(p, rank);

Здесь <tt>countSort()</tt> — сортировка подсчётом:
void countSort(vector<int> &p, const vector<int> &rank) {
int n = p.size();

vector<int> rankCount(n);
for (int i = 0; i < n; i++)
rankCount[rank[i]]++;

vector<int> rankFrom(n);
for (int i = 1; i < n; i++)
rankFrom[i] = rankFrom[i - 1] + rankCount[i - 1];

vector<int> sortedP(n);
for (int elem : p)
sortedP[rankFrom[rank[elem]]++] = elem;
p.swap(sortedP);

== Поиск подстрок ==

int count(const string &s, const vector<int> &p, const string &t) {
int l = 0, r = p.size();
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (s.compare(p[m], t.size(), t) >= 0)
r = m;
else
l = m;
}
int lb = r;

l = 0, r = p.size();
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (s.compare(p[m], t.size(), t) > 0)
r = m;
else
l = m;
}
int ub = r;

return ub - lb;
}

== Ссылки ==
* [http://codeforces.com/edu/course/2/lesson/2 Codeforces — Суффиксный массив]
* [http://e-maxx.ru/algo/suffix_array e-maxx — Суффиксный массив]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2 neerc.info.ru/wiki — Суффиксный массив]
* [http://algorithmica.org/ru/suffix-array Algorithmica.org — Суффиксный массив]
* [http://habr.com/ru/post/115346/ Habr — Суффиксный массив — удобная замена суффиксного дерева]
* [http://visualgo.net/en/suffixarray VisuAlgo — Suffix Array]

Суффиксный массив - История изменений

Ctrlalt в 15:37, 11 апреля 2026

Ctrlalt: /* Ссылки */

Ctrlalt: /* Ссылки */

Ctrlalt в 17:36, 23 февраля 2020

Ctrlalt в 16:46, 23 февраля 2020

Ctrlalt в 16:38, 23 февраля 2020

Ctrlalt: /* Поиск подстрок */

Ctrlalt в 17:51, 22 февраля 2020

Ctrlalt: Новая страница: «== Построение == Построение за Nlog2N: vector makeSuffixArray(string s) { s += '\0'; int n = s.size(); ve…»

Ctrlalt: Новая страница: «== Построение == Построение за Nlog²N: vector makeSuffixArray(string s) { s += '\0'; int n = s.size(); ve…»