{"id":232012,"date":"2023-01-20T19:08:00","date_gmt":"2023-01-20T16:08:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=232012"},"modified":"2023-02-05T13:23:19","modified_gmt":"2023-02-05T10:23:19","slug":"algorytm-pogrubiania-slow-w-html","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/pl\/algorytm-pogrubiania-slow-w-html\/","title":{"rendered":"Algorytm pogrubiania s\u0142\u00f3w w HTML"},"content":{"rendered":"<blockquote>\n<p>Maj\u0105c zestaw s\u0142\u00f3w kluczowych, s\u0142owa i ci\u0105g S, pogrub wszystkie wyst\u0105pienia wszystkich s\u0142\u00f3w kluczowych. Wszelkie litery pomi\u0119dzy <strong>i<\/strong> tagami staj\u0105 si\u0119 pogrubione.<\/p>\n<p>Zwracany ci\u0105g powinien u\u017cywa\u0107 jak najmniejszej mo\u017cliwej liczby tag\u00f3w i oczywi\u015bcie tagi powinny tworzy\u0107 prawid\u0142ow\u0105 kombinacj\u0119.<\/p>\n<p>Na przyk\u0142ad, bior\u0105c pod uwag\u0119, \u017ce s\u0142owa = [\u201eab&quot;, \u201ebc&#8221;] i S = \u201eaabcd&#8221;, powinni\u015bmy zwr\u00f3ci\u0107 \u201ea <strong>abc<\/strong> d&#8221;. Zwr\u00f3\u0107 uwag\u0119, \u017ce zwr\u00f3cenie \u201ea <strong>a<em><\/em><\/strong> b<em><\/em>cd&#8221; spowoduje u\u017cycie wi\u0119kszej liczby tag\u00f3w, wi\u0119c to jest niepoprawne.<\/p>\n<p>Notatka:<\/p>\n<ul>\n<li>s\u0142owa maj\u0105 d\u0142ugo\u015b\u0107 w zakresie [0, 50].<\/li>\n<li>s\u0142owa[i] maj\u0105 d\u0142ugo\u015b\u0107 w przedziale [1, 10].<\/li>\n<li>S ma d\u0142ugo\u015b\u0107 w przedziale [0,500].<\/li>\n<li>Wszystkie znaki w s\u0142owach[i] i S s\u0105 ma\u0142ymi literami.<\/li>\n<\/ul>\n<\/blockquote>\n<h3>Pogrubienie ci\u0105gu za pomoc\u0105 algorytmu Bruteforce<\/h3>\n<p>Bez wymogu najkr\u00f3tszego, mo\u017cemy pogrubi\u0107 ka\u017cde wyst\u0105pienie s\u0142\u00f3w na li\u015bcie. Poniewa\u017c otrzymali\u015bmy oryginalny <a href=\"https:\/\/wordpress.mediadoma.com\/pl\/jak-dodac-wyszukiwarke-google-do-bloga-wordpress-widget-prosty-kod-html\/\" title=\"ci\u0105g HTML\">ci\u0105g HTML<\/a>, mo\u017cemy zaznaczy\u0107 pogrubienie dla ka\u017cdego znaku wyst\u0119puj\u0105cego w pogrubionych s\u0142owach.<\/p>\n<p>Tak wi\u0119c, z przestrzeni\u0105 O(N) i O(NM), gdzie N jest rozmiarem ci\u0105gu, a M jest ca\u0142kowit\u0105 d\u0142ugo\u015bci\u0105 pogrubionego ci\u0105gu, nast\u0119puj\u0105cy <a href=\"https:\/\/helloacm.com\/algorithms-to-find-the-three-numbers-in-array-that-sum-up-to-zero-3sum\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">algorytm bruteforce<\/a> C++ wstawi najmniej pogrubionych tag\u00f3w HTML, kt\u00f3re spe\u0142niaj\u0105 wymagania.<\/p>\n<pre><code>class Solution {\npublic:\n\u00a0 \u00a0 string boldWords(vector&lt;string&gt;&amp; words, string S) {\n\u00a0 \u00a0 \u00a0 \u00a0 int n = S.size();\n\u00a0 \u00a0 \u00a0 \u00a0 vector&lt;bool&gt; bold(n, false);\n\u00a0 \u00a0 \u00a0 \u00a0 for (const auto &amp;s: words) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 for (int i = 0; i + s.size() - 1 &lt; n; ++ i) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 bool ok = true;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 for (int k = 0; k &lt; s.size(); ++ k) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (s[k] != S[i + k]) { \/\/ bold string s not found in the string\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ok = false;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 break;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (ok) { \/\/ it is bold\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 for (int k = 0; k &lt; s.size(); ++ k) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 bold[i + k] = true; \/\/ mark the character bold\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 string ans = \"\";\n\u00a0 \u00a0 \u00a0 \u00a0 for (int i = 0; i &lt; n; ++ i) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/\/ bold start boundary\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (bold[i] &amp;&amp; (i == 0 || !bold[i - 1])) ans += \"&lt;b&gt;\"; \n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ans += S[i];\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/\/ bold end boundary\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if (bold[i] &amp;&amp; (i == n - 1 || !bold[i + 1])) ans += \"&lt;\/b&gt;\";\n\u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 return ans;\n\u00a0 \u00a0 }\n};<\/code><\/pre>\n<p>Po zaznaczeniu pogrubionych znak\u00f3w ponownie skanujemy ci\u0105g i szukamy granic, a nast\u0119pnie wstawiamy odpowiednio tagi.<\/p>\n<p><div id=\"PostUnique_PostSource\" style=\"padding-top: 50px\">\u0179r\u00f3d\u0142o nagrywania:  <a target=\"_blank\" rel=\"noopener nofollow\" href=\"\/\/helloacm.com\" class=\"external external_icon\">helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Algorytm pogrubiania s\u0142\u00f3w w HTML<\/p>\n","protected":false},"author":1,"featured_media":224460,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_wp_rev_ctl_limit":""},"categories":[721,919,897,836,845],"tags":[1169],"class_list":["post-232012","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-deweloper","category-inny","category-kod","category-przewodnik-dla-poczatkujacych","category-samouczki","tag-affiai-pl"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts\/232012","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/comments?post=232012"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts\/232012\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/media\/224460"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/media?parent=232012"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/categories?post=232012"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/tags?post=232012"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}