snipt

Ctrl+h for KB shortcuts

C++

Repeated string

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

bool isRepeated(string s1) {
  size_t N = s1.size();
  string result = s1.substr(0,2);
  int j = 0;
  for (int i = 2; i < N;i++) {
    if (s1[i] == result[j])
      j++;
    else {
      for (; j >= 0; j--) {
        result.push_back(s1[i-j]);
      }
      j = 0;
    }
  }
  return j == result.size();
}



int main() {
  string s = "ababc";
  bool result = isRepeated(s);
  cout << "is " << s << " repeated? " << result << endl;
  return 0;
}
https://snipt.net/embed/d714afe3e59ef7491901a3402a321435/
/raw/d714afe3e59ef7491901a3402a321435/
d714afe3e59ef7491901a3402a321435
cpp
C++
33
2019-06-25T15:44:11
True
False
False
/api/public/snipt/142288/
repeated-string
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><a href="#L-1"> 1</a> <a href="#L-2"> 2</a> <a href="#L-3"> 3</a> <a href="#L-4"> 4</a> <a href="#L-5"> 5</a> <a href="#L-6"> 6</a> <a href="#L-7"> 7</a> <a href="#L-8"> 8</a> <a href="#L-9"> 9</a> <a href="#L-10">10</a> <a href="#L-11">11</a> <a href="#L-12">12</a> <a href="#L-13">13</a> <a href="#L-14">14</a> <a href="#L-15">15</a> <a href="#L-16">16</a> <a href="#L-17">17</a> <a href="#L-18">18</a> <a href="#L-19">19</a> <a href="#L-20">20</a> <a href="#L-21">21</a> <a href="#L-22">22</a> <a href="#L-23">23</a> <a href="#L-24">24</a> <a href="#L-25">25</a> <a href="#L-26">26</a> <a href="#L-27">27</a> <a href="#L-28">28</a> <a href="#L-29">29</a> <a href="#L-30">30</a> <a href="#L-31">31</a> <a href="#L-32">32</a></pre></div></td><td class="code"><div class="highlight"><pre><span></span><span id="L-1"><a name="L-1"></a><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp"></span> </span><span id="L-2"><a name="L-2"></a><span class="cp">#include</span> <span class="cpf">&lt;vector&gt;</span><span class="cp"></span> </span><span id="L-3"><a name="L-3"></a><span class="cp">#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span> </span><span id="L-4"><a name="L-4"></a><span class="cp">#include</span> <span class="cpf">&lt;stack&gt;</span><span class="cp"></span> </span><span id="L-5"><a name="L-5"></a> </span><span id="L-6"><a name="L-6"></a><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> </span><span id="L-7"><a name="L-7"></a> </span><span id="L-8"><a name="L-8"></a><span class="kt">bool</span> <span class="nf">isRepeated</span><span class="p">(</span><span class="n">string</span> <span class="n">s1</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-9"><a name="L-9"></a> <span class="kt">size_t</span> <span class="n">N</span> <span class="o">=</span> <span class="n">s1</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> </span><span id="L-10"><a name="L-10"></a> <span class="n">string</span> <span class="n">result</span> <span class="o">=</span> <span class="n">s1</span><span class="p">.</span><span class="n">substr</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="mi">2</span><span class="p">);</span> </span><span id="L-11"><a name="L-11"></a> <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-12"><a name="L-12"></a> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">N</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-13"><a name="L-13"></a> <span class="k">if</span> <span class="p">(</span><span class="n">s1</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">result</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> </span><span id="L-14"><a name="L-14"></a> <span class="n">j</span><span class="o">++</span><span class="p">;</span> </span><span id="L-15"><a name="L-15"></a> <span class="k">else</span> <span class="p">{</span> </span><span id="L-16"><a name="L-16"></a> <span class="k">for</span> <span class="p">(;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span> </span><span id="L-17"><a name="L-17"></a> <span class="n">result</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">s1</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">]);</span> </span><span id="L-18"><a name="L-18"></a> <span class="p">}</span> </span><span id="L-19"><a name="L-19"></a> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-20"><a name="L-20"></a> <span class="p">}</span> </span><span id="L-21"><a name="L-21"></a> <span class="p">}</span> </span><span id="L-22"><a name="L-22"></a> <span class="k">return</span> <span class="n">j</span> <span class="o">==</span> <span class="n">result</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> </span><span id="L-23"><a name="L-23"></a><span class="p">}</span> </span><span id="L-24"><a name="L-24"></a> </span><span id="L-25"><a name="L-25"></a> </span><span id="L-26"><a name="L-26"></a> </span><span id="L-27"><a name="L-27"></a><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> </span><span id="L-28"><a name="L-28"></a> <span class="n">string</span> <span class="n">s</span> <span class="o">=</span> <span class="s">&quot;ababc&quot;</span><span class="p">;</span> </span><span id="L-29"><a name="L-29"></a> <span class="kt">bool</span> <span class="n">result</span> <span class="o">=</span> <span class="n">isRepeated</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> </span><span id="L-30"><a name="L-30"></a> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&quot;is &quot;</span> <span class="o">&lt;&lt;</span> <span class="n">s</span> <span class="o">&lt;&lt;</span> <span class="s">&quot; repeated? &quot;</span> <span class="o">&lt;&lt;</span> <span class="n">result</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span> </span><span id="L-31"><a name="L-31"></a> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-32"><a name="L-32"></a><span class="p">}</span> </span></pre></div> </td></tr></table>
"linear complexity", repeated, string
--- 
+++ 
@@ -8,24 +8,24 @@
 bool isRepeated(string s1) {
   size_t N = s1.size();
   string result = s1.substr(0,2);
-  size_t j = 0;
-  for (size_t i = 2; i < N;i++) {
+  int j = 0;
+  for (int i = 2; i < N;i++) {
     if (s1[i] == result[j])
       j++;
     else {
-      /// add mismatched charachters to result and reset j
       for (; j >= 0; j--) {
         result.push_back(s1[i-j]);
       }
+      j = 0;
     }
   }
-  return j == result.size() + 1;
+  return j == result.size();
 }
 
 
 
 int main() {
-  string s = "abcabc";
+  string s = "ababc";
   bool result = isRepeated(s);
   cout << "is " << s << " repeated? " << result << endl;
   return 0;
--- 
+++ 
@@ -0,0 +1,32 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <stack>
+
+using namespace std;
+
+bool isRepeated(string s1) {
+  size_t N = s1.size();
+  string result = s1.substr(0,2);
+  size_t j = 0;
+  for (size_t i = 2; i < N;i++) {
+    if (s1[i] == result[j])
+      j++;
+    else {
+      /// add mismatched charachters to result and reset j
+      for (; j >= 0; j--) {
+        result.push_back(s1[i-j]);
+      }
+    }
+  }
+  return j == result.size() + 1;
+}
+
+
+
+int main() {
+  string s = "abcabc";
+  bool result = isRepeated(s);
+  cout << "is " << s << " repeated? " << result << endl;
+  return 0;
+}