Настройки поиска (Страница 3 из 4)

epic fail...
Возникла проблема в реализации.. .Когда вычисляю h(i..j) это значение иногда бывает отрицательное(понятно по какой причине).Перечитывал статью,но ошибку в самом алгоритме не нашёл.Но в коде,несмотря на то, что я ничего не понимаю в с++, меня насторожила запись в коде: "{
    h(i) = (t(i) - 'a' + 1) * p_pow(i);
    if (i)  h(i) += h(i-1);
}
"
что означает if (i)?и как избежать искажений из-за вычислений по модулю?

Хммм..
Например при поиске вхождений строки s1 в s мы найдём хэш-функции от всех префиксов строки s и от самой  s1.А потом при поиске проверяем чтобы  h(s1)*P^(i-1)=h(j)-h(i).
Так ведь?

Я как паскальщик на код даже не смотрю=)Может это и к лучшему..:)

оО
Хорошая идея=)
Я думаю что это правильно из-за того,что вершины которые а МОДе будут соединены будут "соседями" либо по х,либо по у,либо z.Даже если в одной из сортировок мы выбрали не "правильное" ребро между вершинами u и v ,то одна из вершин которая будет лежать на отрезке num1 и num2(номерами u и v)  в других сортировках станет промежуточной в МОДе между u и v(но никакая другая!!!(только между нум1 и нум2!!!)).
Это правильно?

По-моему тебе нужно это.
http://e-maxx.ru/algo/vertex_weighted_matching
но ,возможно,я ошибаюсь)

В орграфе намного проще.
А в неориентрированом сложнее....

Я снова в заблуждении
Вот 2 моих варианта ЮНИОНа:
1:
  a:=findset(x);
  b:=findset(y);
  dsu[a]:=b;
2:
  a:=findset(x);
  b:=findset(y);
  if random(2)=1 then swap(a,b);
  dsu[a]:=b;

Я не понимаю в чём первый вариант проигрывает второму?(оО)

Я не очень силён в строках,но для таких ограничений можно взять массив логического типа где b(i)=true,если символ s(i)-выделен.И по окончанию поиска подстроки считаем количество b(i)=true для всех i(1..length(s)).Ну а сам поиск лучше реализовать через КМП.

Вот ссылка на раздел где есть теория и сами задачи на структуры данных и на дерево отрезков в том числе- http://informatics.mccme.ru/moodle/cour … .php?id=18