Изменения

'''struct ''' Node { '''Node* ''' son[SZ]; <font color=green>// массив сыновей; SZ - это размер алфавита</font> '''Node* ''' go[SZ]; <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии)</font> '''Node* ''' parent; <font color=green>// вершина родитель</font> '''Node* ''' suffLink; <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font> '''Node* ''' up; <font color=green>// сжатая суффиксная ссылка</font> '''char ''' charToParent; <font color=green>// символ, ведущий к родителю</font> '''bool ''' leaf; <font color=green>// флаг, является ли вершина терминалом</font> std::'''vector<int> ''' leafPatternNumber; <font color=green>// номера образцов, за которые отвечает терминал</font> };

'''Node* ''' getSuffLink(v : '''Node* v''') { '''if ''' ('''not'''(!v->suffLink) { ) <font color=green>// если суффиксная ссылка ещё не вычислена</font> '''if ''' (v == root || '''or''' v->parent == root) { v->suffLink = root; } '''else {''' v->suffLink = getGo(getSuffLink(v->parent), v->charToParent); } } '''return ''' v->suffLink; }

'''Node* ''' getGo(v : '''Node* v''', c : '''char c''') { '''if ''' (not(!v->go[c]) { ) <font color=green>// если переход по символу c ещё не вычислен</font> '''if ''' (v->son[c]) {

} '''else {'''

} } '''return ''' v->go[c]; }

'''Node* ''' getUp(c : '''Node* v''') { '''if ''' (not(!v->up) { ) <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font> '''if ''' (getSuffLink(v)->leaf) { v->up = getSuffLink(v); } '''else ''' '''if ''' (getSuffLink(v) == root) { v->up = root; } '''else {''' v->up = getUp(getSuffLink(v)); } } '''return ''' v->up; }

void '''fun''' addString(std:s :'''string const& s''', patternNumber : '''int patternNumber''') { '''Node* ''' cur = root; '''for ''' ('''int ''' i = 0; i < ..s.length(); ++i- 1) { '''char ''' c = s[i] - 'a'; '''if ''' (cur->son[c] == 0) {

cur->son[c]->suffLink = 0; cur->son[c]->up = 0; cur->son[c]->parent = cur; cur->son[c]->charToParent = c; cur->son[c]->leaf = ''false; }'' cur = cur->son[c]; } cur->leaf = '''true;''' cur->leafPatternNumber.push_back(patternNumber); }

void '''fun''' processText(std:t :'''string const& t''', std:found :'''vector<bool>& found''') { <font color=green>// found - это вектор, длина которого равна количеству образцов</font> found.assign(w, '''false'''); <font color=green>// w - количество образцов</font> '''Node* ''' cur = root; '''for ''' ('''int ''' i = 0; i < ..t.length(); ++i- 1) { '''char ''' c = t[i] - 'a'; cur = getGo(cur, c); '''for ''' ('''int ''' j = 0; j < ..cur->leafPatternNumber.size(); ++j- 1) { found[cur->leafPatternNumber[j]] = '''true; }'''