{"id":297139,"date":"2020-01-14T21:00:08","date_gmt":"2020-01-14T21:00:08","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=297139"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=297139","title":{"rendered":"\u041e\u0445 \u0443\u0436 \u044d\u0442\u043e\u0442 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u0439 C\/C++"},"content":{"rendered":"\n
\u042d\u0442\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043f\u043e\u0434\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0438\u0442\u043e\u0433\u043e\u0432 \u043d\u0430 \u043f\u043e\u0441\u0442 \u201c\u0411\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c C++; \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c PHP\u201d<\/a><\/p>\n

\u041d\u0435\u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u043b\u043e \u2014 \u00ab\u0441\u043f\u043e\u0440\u0438\u0442\u044c\u00bb \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u044e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u044b\u0441\u043b\u0435\u0439 \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0441\u0442. \u0410\u0432\u0442\u043e\u0440 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u043b \u0442\u0443\u0442<\/a>, \u0442\u0443\u0442<\/a>, \u0438 \u0435\u0449\u0435 \u043c\u043d\u043e\u0433\u043e \u0433\u0434\u0435<\/a>, \u0447\u0442\u043e \u0443 \u043d\u0435\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0441\u0442\u0430\u0436 \u0438 \u0431\u043e\u0433\u0430\u0442\u044b\u0439 \u043e\u043f\u044b\u0442 \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043d\u0430 \u0421++.
<\/a>
\u0418\u0442\u0430\u043a, \u043c\u044b \u0438\u043c\u0435\u0435\u043c \u0434\u0435\u0441\u044f\u0442\u043e\u043a \u00ab\u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e\u00bb \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0430 \u043d\u0430 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u044f\u0437\u044b\u043a\u0430\u0445, \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0431\u0443\u0434\u0435\u043c \u0438\u0437 \u043d\u0438\u0445 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0430 C \u0438 C++ <\/p>\n

\u043a\u043e\u0434 C<\/b><\/p>\n
\n
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h>  static long lev_dist (const char *s1,           const char *s2) {     unsigned long m, n;     unsigned long i, j;     long *v0, *v1;     long ret, *temp;      m = strlen (s1);     n = strlen (s2);      \/* Edge cases. *\/     if (m == 0) {         return n;     } else if (n == 0) {         return m;     }      v0 = malloc (sizeof (long) * (n + 1));     v1 = malloc (sizeof (long) * (n + 1));      if (v0 == NULL || v1 == NULL) {         fprintf (stderr, \"failed to allocate memory\\n\");         exit (-1);     }      for (i = 0; i <= n; ++i) {         v0[i] = i;     }     memcpy (v1, v0, n + 1);      for (i = 0; i < m; ++i) {         v1[0] = i + 1;          for (j = 0; j < n; ++j) {             const long subst_cost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);             const long del_cost = v0[j + 1] + 1;             const long ins_cost = v1[j] + 1;  #if !defined(__GNUC__) || defined(__llvm__)             if (subst_cost < del_cost) {                 v1[j + 1] = subst_cost;             } else {                 v1[j + 1] = del_cost;             } #else             v1[j + 1] = (subst_cost < del_cost) ? subst_cost : del_cost; #endif             if (ins_cost < v1[j + 1]) {                 v1[j + 1] = ins_cost;             }         }          temp = v0;         v0 = v1;         v1 = temp;     }      ret = v0[n];     free (v0);     free (v1);     return ret; }  int main () {     const int len = 15000;     int i;     char s1[15001], *s2 = s1, s3[15001];     clock_t start_time, exec_time;      for (i = 0; i < len; ++i) {         s1[i] = 'a';         s3[i] = 'b';     }     s1[len] = s3[len] = '\\0';      start_time = clock ();      printf (\"%ld\\n\", lev_dist (s1, s2));     printf (\"%ld\\n\", lev_dist (s1, s3));      exec_time = clock () - start_time;     fprintf (stderr,              \"Finished in %.3fs\\n\",              ((double) exec_time) \/ CLOCKS_PER_SEC);     return 0; }<\/code><\/pre>\n
  <\/div>\n<\/div>\n
  <\/p>\n
\u041a\u043e\u0434 C++<\/b><\/p>\n
\n
#include <algorithm> #include <iostream> #include <numeric> #include <vector> #include <string>  size_t lev_dist(const std::string& s1, const std::string& s2) {   const auto m = s1.size();   const auto n = s2.size();    std::vector<int64_t> v0;   v0.resize(n + 1);   std::iota(v0.begin(), v0.end(), 0);    auto v1 = v0;    for (size_t i = 0; i < m; ++i)   {     v1[0] = i + 1;      for (size_t j = 0; j < n; ++j)     {       auto delCost = v0[j + 1] + 1;       auto insCost = v1[j] + 1;       auto substCost = s1[i] == s2[j] ? v0[j] : (v0[j] + 1);        v1[j + 1] = std::min({ delCost, insCost, substCost });     }      std::swap(v0, v1);   }    return v0[n]; }  int main() {     std::string s1(20000, 'a');     std::string s2(20000, 'a');     std::string s3(20000, 'b');      std::cout << lev_dist(s1, s2) << std::endl;     std::cout << lev_dist(s1, s3) << std::endl; }<\/code><\/pre>\n
  <\/div>\n<\/div>\n
\u0422\u0440\u0438 \u0433\u0440\u0443\u0431\u0435\u0439\u0448\u0438\u0435 \u043e\u0448\u0438\u0431\u043a\u0438:<\/h4>\n
  <\/p>\n