Коды основных функций / [Код основных функций] Лаб. 2. Часть 2
.pdf
[Код основных функций] Лабораторная работа №2. Часть 2. Поиск подстрок
//Get the current time.
//This function should be used only for measuring time
//(first call, algorithm, second call; then the difference between the values) double getProcTime() {
#if defined(_WIN32) // If Windows:
FILETIME createTime, exitTime, kernelTime, userTime;
if (GetProcessTimes(GetCurrentProcess(), &createTime, &exitTime, &kernelTime, &userTime) != -1)
return (ULARGE_INTEGER { {userTime.dwLowDateTime, userTime.dwHighDateTime } }).QuadPart / 10000000.L;
return 0;
#else // If Linux or MacOS:
return double(clock()) / CLOCKS_PER_SEC; #endif
}
//Standard search
template <class T = std::string>
int standardSearch(const T & str, const T & substr, int pos = 0) noexcept { return str.find(substr, pos);
}
// Direct search
template <class T = std::string>
int directSearch(const T & str, const T & substr, int pos = 0) { const int n = str.size() - pos, m = substr.size();
if (m == 0) return (n >= 0) ? pos : -1; if (n <= 0 || n < m) return -1;
for (int i, j = 0, end = n - m; j <= end; ++j) {
for (i = 0; i < m && str[i + j + pos] == substr[i]; ++i); if (i < m) continue;
return j + pos;
}
return -1;
}
// Boyer-Moore-Horspool search template <class T = std::string>
int boyerMooreHorspoolSearch(const T & str, const T & substr, int pos = 0) { const int n = str.size() - pos, m = substr.size();
if (m == 0) return (n >= 0) ? pos : -1; if (n <= 0 || n < m) return -1;
int * badchar = new int[UCHAR_MAX + 1];
// memset. Attention! The second argument is interpreted as unsigned char. -1 : 0xFF. memset(badchar, -1, sizeof(int) * (UCHAR_MAX + 1));
for (int i = 0; i < m; ++i) badchar[(unsigned char) substr[i]] = i;
for (int s = 0, j, end = n - m; s <= end; s += std::max(1, j - badchar[(unsigned char) str[s + j + pos]])) {
for (j = m - 1; j >= 0 && str[s + j + pos] == substr[j]; --j); if (j >= 0) continue;
delete[] badchar; return s + pos;
}
delete[] badchar; return -1;
}
//Apostolico-Crochemore search template <class T = std::string>
int apostolicoCrochemoreSearch(const T & str, const T & substr, int pos = 0) { const int n = str.size() - pos, m = substr.size();
if (m == 0) return (n >= 0) ? pos : -1; if (n <= 0 || n < m) return -1;
int * taggedBorder = new int[m + 1];
for (int i = 0, j = taggedBorder[0] = -1; i < m; ) { while (j >= 0 && substr[i] != substr[j])
j = taggedBorder[j]; ++i, ++j;
taggedBorder[i] = (i < m && substr[i] == substr[j]) ? taggedBorder[j] : j;
}
int L;
for (L = 1; L < m && substr[L - 1] == substr[L]; ++L); if (L == m) L = 0;
for (int i = L, j = 0, k = 0, end = n - m; j <= end; ) { while (i < m && substr[i] == str[i + j + pos]) ++i; if (i >= m) {
while (k < L && substr[k] == str[j + k + pos]) ++k; if (k >= L) {
delete[] taggedBorder; return j + pos;
}
}
j += i - taggedBorder[i]; if (i == L)
k = std::max(0, k - 1); else if (taggedBorder[i] <= L)
k = std::max(0, taggedBorder[i]), i = L; else
k = L, i = taggedBorder[i];
}
delete[] taggedBorder; return -1;
}
//Knuth-Morris-Pratt search
template <class T = std::string>
int knuthMorrisPrattSearch(const T & str, const T & substr, int pos = 0) { const int n = str.size() - pos, m = substr.size();
if (m == 0) return (n >= 0) ? pos : -1; if (n <= 0 || n < m) return -1;
int * kmpNext = new int[m + 1];
for (int i = 0, j = kmpNext[0] = -1; i < m; ) { while (j > -1 && substr[i] != substr[j])
j = kmpNext[j]; ++i, ++j;
kmpNext[i] = (i < m && substr[i] == substr[j]) ? kmpNext[j] : j;
}
for (int i = 0, j = 0; i < n; ) {
while (j > -1 && substr[j] != str[i + pos]) j = kmpNext[j];
++i;
if (++j < m) continue; delete[] kmpNext; return i - j + pos;
}
delete[] kmpNext; return -1;
}
// Boyer-Moore search
template <class T = std::string>
int boyerMooreSearch(const T & str, const T & substr, int pos = 0) { const int n = str.size() - pos, m = substr.size();
if (m == 0) return (n >= 0) ? pos : -1; if (n <= 0 || n < m) return -1;
int * bG = new int[m], * bB = new int[UCHAR_MAX + 1], * suff = new int[m]; for (int i = 0; i < m; ++i) bG[i] = m;
for (int i = 0; i <= UCHAR_MAX; ++i) bB[i] = m; suff[m - 1] = m;
for (int i = m - 2, g = m - 1, f = 0; i >= 0; --i) if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f]; else {
if (i < g) g = i; f = i;
while (g >= 0 && substr[g] == substr[g + m - 1 - f]) --g; suff[i] = f - g;
}
for (int i = m - 1, j = 0; i >= 0; --i) if (suff[i] == i + 1)
for (int end = m - 1 - i; j < end; ++j) if (bG[j] == m)
bG[j] = end;
for (int i = 0, end = m - 1; i < end; ++i)
bB[(unsigned char) substr[i]] = bG[end - suff[i]] = end - i;
for (int i, j = 0, end = n - m; j <= end; j += std::max(bG[i], bB[(unsigned char) str[i + j + pos]] + i + 1 - m)) {
for (i = m - 1; i >= 0 && substr[i] == str[i + j + pos]; --i); if (i >= 0) continue;
delete[] bG, delete[] bB, delete[] suff; return j + pos;
}
delete[] bG, delete[] bB, delete[] suff; return -1;
}
// Turbo-Boyer-Moore search template <class T = std::string>
int turboBoyerMooreSearch(const T & str, const T & substr, int pos = 0) { const int n = str.size() - pos, m = substr.size();
if (m == 0) return (n >= 0) ? pos : -1; if (n <= 0 || n < m) return -1;
int * bG = new int[m], * bB = new int[UCHAR_MAX + 1], * suff = new int[m]; for (int i = 0; i < m; ++i) bG[i] = m;
for (int i = 0; i <= UCHAR_MAX; ++i) bB[i] = m; suff[m - 1] = m;
for (int i = m - 2, g = m - 1, f = 0; i >= 0; --i) if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f]; else {
if (i < g) g = i; f = i;
while (g >= 0 && substr[g] == substr[g + m - 1 - f]) --g; suff[i] = f - g;
}
for (int i = m - 1; i >= 0; --i) if (suff[i] == i + 1)
for (int j = 0, end = m - i - 1; j < end; ++j) if (bG[j] == m)
bG[j] = end;
for (int i = 0, end = m - 1; i < end; ++i)
bB[int((unsigned char) substr[i])] = bG[end - suff[i]] = end - i; for (int j = 0, u = 0, shift = m, end = n - m; j <= end; j += shift) {
int i = m - 1;
while (i >= 0 && substr[i] == str[i + j + pos]) { --i;
if (u != 0 && i == m - 1 - shift) i -= u;
}
if (i < 0) {
delete[] bG, delete[] bB, delete[] suff; return j + pos;
}
int v = m - 1 - i, tShift = u - v, bcShift = bB[int((unsigned char) str[i + j + pos])] -
m + 1 + i;
shift = std::max({ tShift, bcShift, bG[i] }); if (shift == bG[i])
u= std::min(m - shift, v); else {
if (tShift < bcShift)
shift = std::max(shift, u + 1);
u= 0;
}
}
delete[] bG, delete[] bB, delete[] suff; return -1;
}
// Colussi search
template <class T = std::string>
int colussiSearch(const T & str, const T & substr, int pos = 0) noexcept(false) { const int n = str.size() - pos, m = substr.size();
if (m == 0) return (n >= 0) ? pos : -1; if (n <= 0 || n < m) return -1;
int * h = new int[m], * next = new int[m + 1], * shift = new int[m + 1], * hmax = new int[m + 1],
* kmin = new int[m] {0}, * nhd0 = new int[m], * rmin = new int[m]; for (int i = 1, k = 1; k <= m; ) {
while (i < m && substr[i] == substr[i - k]) ++i; hmax[k] = i;
int q = k + 1;
while (hmax[q - k] + k < i) hmax[q] = hmax[q - k] + k, ++q;
k = q;
if (k == i + 1) i = k;
}
for (int i = m; i > 0; --i) if (hmax[i] < m)
kmin[hmax[i]] = i;
for (int i = m - 1, r = 0; i >= 0; --i) { if (hmax[i + 1] == m) r = i + 1; rmin[i] = (kmin[i] == 0) ? r : 0;
}
int s = -1;
for (int i = 0, r = m; i < m; ++i) h[((kmin[i] == 0) ? --r : ++s)] = i;
int nd = s;
for (int i = 0; i <= nd; ++i) shift[i] = kmin[h[i]];
for (int i = nd + 1; i < m; ++i) shift[i] = rmin[h[i]];
shift[m] = rmin[0]; s = 0;
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.