Алгоритм Ахо-Корасик - История изменений

Ctrlalt в 13:01, 10 сентября 2023

2023-09-10T13:01:36Z

← Предыдущая версия		Версия от 13:01, 10 сентября 2023
Строка 93:		Строка 93:
	vector<int> termIndexes;		vector<int> termIndexes;
	Vertex *termLink = 0;		Vertex *termLink = 0;
	~~map~~<char, Vertex> next;		unordered_map<char, Vertex> next;
	Vertex *sufLink = 0;		Vertex *sufLink = 0;
	~~map~~<char, Vertex *> autLink;		unordered_map<char, Vertex *> autLink;
	} root;		} root;
	int stringCount = 0;		int stringCount = 0;

Ctrlalt в 13:00, 10 сентября 2023

2023-09-10T13:00:38Z

@@ Строка 1: / Строка 1: @@
 Автомат Ахо-Корасик позволяет находить в тексте вхождения любой строки из заданного набора строк.
@@ Строка 13: / Строка 15: @@
 Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (набор строк — ABA и B, текст — AB, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.
   class Trie {
       struct Vertex {
-          bool isTerminal = false;
+          bool isTerminal = 0;
           map<char, Vertex> next;
-          Vertex *sufLink = nullptr;
+          Vertex *sufLink = 0;
           map<char, Vertex *> autLink;
       } root;
   public:
-      void add(const string &s) {
+      void insert(const string &s) {
           Vertex *v = &root;
-          for (const char &c : s)
+          for (char c : s)
               v = &v->next[c];
-          v->isTerminal = true;
+          v->isTerminal = 1;
+      }
@@ Строка 57: / Строка 77: @@
       bool check(const string &s) {
           Vertex *v = &root;
-          for (const char &c : s) {
+          for (char c : s) {
               v = v->autLink[c];
               if (v->isTerminal)
-                  return true;
+                  return 1;
+          }
-          return false;
+      }
   };
 == Ссылки ==

Ctrlalt в 01:03, 7 сентября 2023

2023-09-07T01:03:07Z

← Предыдущая версия		Версия от 01:03, 7 сентября 2023
Строка 32:		Строка 32:
	void build(int alphabetSize) {		void build(int alphabetSize) {
	queue<Vertex *> q;		queue<Vertex *> q;
			root.sufLink = &root;
	q.push(&root);		q.push(&root);

Ctrlalt в 00:59, 7 сентября 2023

2023-09-07T00:59:57Z

← Предыдущая версия		Версия от 00:59, 7 сентября 2023
Строка 12:		Строка 12:
	* Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].		* Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].

	Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (~~текст — AAB,~~ набор строк — ~~AAA~~ и B, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.		Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (набор строк — ABA и B, текст — AB, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.

	class Trie {		class Trie {
Строка 32:		Строка 32:
	void build(int alphabetSize) {		void build(int alphabetSize) {
	queue<Vertex *> q;		queue<Vertex *> q;
	~~root.sufLink = &root;~~
	q.push(&root);		q.push(&root);

Ctrlalt в 20:22, 21 сентября 2022

2022-09-21T20:22:22Z

← Предыдущая версия		Версия от 20:22, 21 сентября 2022
Строка 47:		Строка 47:
	if (v->next.count(c))		if (v->next.count(c))
	v->autLink[c] = &v->next[c];		v->autLink[c] = &v->next[c];
	else ~~if (v == &root)~~		else
	v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]);		v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]);
	}		}

Ctrlalt в 12:15, 8 сентября 2022

2022-09-08T12:15:07Z

← Предыдущая версия		Версия от 12:15, 8 сентября 2022
Строка 12:		Строка 12:
	* Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].		* Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].

	Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (текст — AAB, набор строк — AAA и B, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной вершина v->sufLink.		Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (текст — AAB, набор строк — AAA и B, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.

	class Trie {		class Trie {

Ctrlalt в 14:58, 7 сентября 2022

2022-09-07T14:58:57Z

@@ Строка 1: / Строка 1: @@
   class Trie {
       struct Vertex {
@@ Строка 32: / Строка 47: @@
                   if (v->next.count(c))
                       v->autLink[c] = &v->next[c];
-                  else
+                  else if (v == &root)
                       v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]);
+              }

Ctrlalt в 20:56, 24 сентября 2020

2020-09-24T20:56:44Z

← Предыдущая версия		Версия от 20:56, 24 сентября 2020
Строка 1:		Строка 1:
	~~<!--~~class Trie {		class Trie {
	struct Vertex {		struct Vertex {
	bool isTerminal = false;		bool isTerminal = false;
Строка 49:		Строка 49:
	return false;		return false;
	}		}
	};~~-->~~		};

	== Ссылки ==		== Ссылки ==

Ctrlalt в 10:58, 18 сентября 2020

2020-09-18T10:58:41Z

← Предыдущая версия		Версия от 10:58, 18 сентября 2020
Строка 1:		Строка 1:
	class Trie {		<!--class Trie {
	struct Vertex {		struct Vertex {
	bool isTerminal = false;		bool isTerminal = false;
Строка 49:		Строка 49:
	return false;		return false;
	}		}
	};		};-->

	== Ссылки ==		== Ссылки ==

Ctrlalt в 00:24, 18 сентября 2020

2020-09-18T00:24:23Z

← Предыдущая версия		Версия от 00:24, 18 сентября 2020
Строка 29:		Строка 29:
	}		}

	for (char c = ' '; c < ' ' + alphabetSize; c++) {		for (char c = 'a'; c < 'a' + alphabetSize; c++) {
	if (v->next.count(c))		if (v->next.count(c))
	v->autLink[c] = &v->next[c];		v->autLink[c] = &v->next[c];