StoneHaos

m_mod_3

Mar 29th, 2021
616
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. int BMSearch(string str, string substr)
  8. {
  9.     vector<int> arr;
  10.     for (int i = 0; i <= str.size() - substr.size(); i++)
  11.     {
  12.         if (str[i] == substr[0])
  13.         {
  14.             arr.push_back(i);
  15.         }
  16.     }
  17.     for (int i = 0; i < arr.size(); ++i)
  18.     {
  19.         int j = arr[i] + substr.size() - 1;
  20.         int k = substr.size() - 1;
  21.         while (k >= 0 && str[j] == substr[k])
  22.         {
  23.             j--;
  24.             k--;
  25.         }
  26.         if (k == -1)
  27.         {
  28.             return arr[i];
  29.         }
  30.     }
  31.     return -1;
  32. }
  33.  
  34. int BFSearch(string str, string substr)
  35. {
  36.     for (int i = 0; i < str.size() - substr.size(); ++i)
  37.     {
  38.         int j = i;
  39.         int k = 0;
  40.         while (k < substr.size())
  41.         {
  42.             if (str[j] != substr[k])
  43.             {
  44.                 break;
  45.             }
  46.             j++;
  47.             k++;
  48.         }
  49.         if (k == substr.size())
  50.         {
  51.             return i;
  52.         }
  53.     }
  54.     return -1;
  55. }
  56.  
  57. int main(void)
  58. {
  59.     setlocale(LC_ALL, "Russian");
  60.     string str, substr;
  61.     cout << "Введите строку:" << endl;
  62.     cin >> str;
  63.     cout << "Введите подстроку:" << endl;
  64.     cin >> substr;
  65.     cout << "Поиск Бойера Мура: " << BMSearch(str, substr) << endl;
  66.     cout << "Прямой поиск: " << BFSearch(str, substr) << endl;
  67.     return 0;
  68. }
RAW Paste Data