Blogs Hub

by AskGif | Sep 01, 2018 | Category :coding

How to find the longest border of a string?

How to find the longest border of a string?

<p>The border of a string is a substring which is both a proper prefix and proper suffix of the string &mdash; "proper" meaning that the whole string does not count as a substring. The longest border of x is "ab". The longest border of y is "abab" (the prefix and suffix can overlap).</p> <p>More details can be found at the link: https://en.wikipedia.org/wiki/Substring#Border</p> <p>&nbsp;</p> <p>e.g&nbsp;</p> <p>abcdabc - border string is abc - length is 3</p> <p>ababab - border string is abab - length is 4</p> <p>&nbsp;</p> <p>C++&nbsp;solution/ Algorithm for border string is as below.</p> <pre class="language-cpp"><code>#include &lt;string&gt; #include &lt;vector&gt; #include &lt;iostream&gt; using namespace std; int longestBorder(const string&amp; s) { int len = s.length(); vector&lt;int&gt; prefixFunc(len); prefixFunc[0] = 0; int curBorderLen = 0; for (int i = 1; i &lt; len; ++i) { while (curBorderLen &gt; 0 &amp;&amp; s[curBorderLen] != s[i]) curBorderLen = prefixFunc[curBorderLen - 1]; if (s[curBorderLen] == s[i]) ++curBorderLen; prefixFunc[i] = curBorderLen; } return prefixFunc[len-1]; } int main() { string s; cin &gt;&gt; s; cout &lt;&lt; longestBorder(s) &lt;&lt; endl; } </code></pre> <p>Time Complexity: O(n)</p> <p>Ideone -&nbsp;<a title="https://ideone.com/UIjwSG" href="https://ideone.com/UIjwSG" target="_blank" rel="noopener">https://ideone.com/UIjwSG</a>&nbsp;</p>

read more...