Материал: [Код основных функций] Лаб. 2. Часть 2

for (int i = 0; i < m; ++i) { nhd0[i] = s;

if (kmin[i] > 0) ++s;

}

for (int i = 0; i <= nd; ++i) next[i] = nhd0[h[i] - kmin[h[i]]];

for (int i = nd + 1; i < m; ++i) next[i] = nhd0[m - rmin[h[i]]];

next[m] = nhd0[m - rmin[h[m - 1]]];

for (int i = 0, j = 0, last = -1, end = n - m; j <= end; j += shift[i], i = next[i]) { while (i < m && last < j + h[i] && substr[h[i]] == str[j + h[i] + pos]) ++i; if (i < m && last < j + h[i]) {

if (i > nd) last = j + m - 1; continue;

}

delete[] h, delete[] next, delete[] shift, delete[] hmax, delete[] kmin, delete[] nhd0, delete[] rmin;

return j + pos;

}

delete[] h, delete[] next, delete[] shift, delete[] hmax, delete[] kmin, delete[] nhd0, delete[] rmin;

return -1;

}

Пройденное тестирование:

1.Пустая строка («» в «» с индекса 0 встречается, «» в «» с индекса 1 не встречается, то есть результат равен -1; также непустые подстроки; где «» – это пустая строка).

2.Строка с одним символом («» в «1» с индекса 0 встречается, «» в «1» с индекса 1 тоже встречается, а с индекса 2 не встречается; также непустые подстроки).

3.Длинная строка с единственным уникальным элементом (если подстрокой является сама строка и поиск осуществляется с индекса 0, то результирующий индекс 0, иначе -1).

4.Простая строка (поиск префиксов и суффиксов в простой строке; также поиск подстрок длиной 2, реверсивных [обратных] подстрокам исходной строки).

5.Простые тесты. Одна строка на все простые тесты, а поиск с разных позиций.

6.Сложные тесты. Генерация новой строки раз в 50 итераций, поиск с разных позиций.

7.На время. 1) Короткие строки, короткие подстроки; 2) Короткие строки, длинные подстроки; 3) Длинные строки, короткие подстроки; 4) Длинные строки, длинные подстроки. Также важен размер используемого алфавита (например, 62, 90 и 230 символов).

Проверка осуществляется сравнением подстроки с результативного индекса (длиной исходной подстроки) и подстроки с результативного индекса (длиной исходной подстроки) стандартного поиска C++ std::find.