First, let me tell you what the border of a string is,
let x = "abacab" let y = "ababab" The border of a string is a substring which is both a proper prefix and proper suffix of the string — "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).
Another example:
In string "abcde hgrab abcde", then "abcde" is a prefix as well as suffix. Thus it is also the longest border of the string above.
How can I find the longest border of a string?
9 Answers
Answers 1
x = abacab y = String.reverse(x) border = "" if (x == y) { print border; return; } for (int i = 0; i < x.length; i++) { if (x[i] == y[i]) border += x[i] else break } print border Answers 2
Finding the "border of a string" is what the prefix function (also known as failure function) of Knuth-Morris-Pratt algorithm do. Implementation in c++ (a bit changed version of this code):
int longestBorder(const string& s) { int len = s.length(); vector<int> prefixFunc(len); prefixFunc[0] = 0; int curBorderLen = 0; for (int i = 1; i < len; ++i) { while (curBorderLen > 0 && s[curBorderLen] != s[i]) curBorderLen = prefixFunc[curBorderLen - 1]; if (s[curBorderLen] == s[i]) ++curBorderLen; prefixFunc[i] = curBorderLen; } return prefixFunc[len-1]; } Runnable version: http://ideone.com/hTW8FL
The complexity of this algorithm is O(n).
Answers 3
Here's a Java implementation, based on the assumption that borders are proper substrings. (Otherwise the longest border is simply the string length.)
public static int findLongestBorder(String s) { int len = s.length(); for (int i = len - 1; i > 0; i--) { String prefix = s.substring(0, i); String suffix = s.substring(len - i, len); if (prefix.equals(suffix)) { return i; } } return 0; } This could be optimized a bit by starting with the string's character array and then comparing individual characters, but the idea behind the algorithm is clearer the way I wrote it.
Answers 4
Here is a JS solution with commentary that uses the prefix function that DAIe mentioned:
function getPrefixBorders(string) { // This will contain the border length for each // prefix in ascending order by prefix length. var borderLengthByPrefix = [0]; // This is the length of the border on the current prefix. var curBorderLength = 0; // Loop from the 2nd character to the last. for (var i = 1; i < string.length; i++) { // As long as a border exists but the character // after it doesn't match the current character, while (curBorderLength > 0 && string[curBorderLength] !== string[i]) // set the border length to the length of the current border's border. curBorderLength = borderLengthByPrefix[curBorderLength - 1]; // If the characters do match, if (string[curBorderLength] === string[i]) // the new border is 1 character longer. curBorderLength++; // Note the border length of the current prefix. borderLengthByPrefix[i] = curBorderLength; } return borderLengthByPrefix; } It returns the longest border lengths of every prefix in a string (which is a lot more than asked for, but it does so in linear time). So to get the length of the longest border in the full string:
var string = "ababab"; var borderLengthsByPrefix = getPrefixBorders(); // [0,0,1,2,3,4] var stringBorderLength = borderLengthsByPrefix[borderLengthsByPrefix.length - 1]; Another great resource for understanding how this works is this video (and the one before it) on Coursera.
Answers 5
To get the length of the longest border, do this:
def get_border_size(astr): border = 0 for i in range(len(astr)): if astr[:i] == astr[-i:]: border = i return border To get the longest border itself, this:
def get_border(astr): border = 0 for i in range(len(astr)): if astr[:i] == astr[-i:]: border = astr[:i] return border Answers 6
I've made a solution using Python3 (works also with Python2), using Counter from collections module and max().
Here is my solution:
from collections import Counter def get_seq(a): data = [] for k in range(1, len(a)): data.append(a[:k]) data.append(a[k:]) return Counter(data) def get_max_sublist(a): bb = [k for k in a.items() if k[1] > 1] try: k, j = max(bb, key= lambda x: len(x[0])) n, _ = max(a.items(), key= lambda x: x[1]) except ValueError: return None else: return k if j > 1 else n seq = ["abacab", "ababab", "abxyab", "abxyba", "abxyzf", "bacab"] for k in seq: j = get_seq(k) print("longest border of {} is: {}".format(k, get_max_sublist(j))) Output:
longest border of abacab is: ab longest border of ababab is: abab longest border of abxyab is: ab longest border of abxyba is: a longest border of abxyzf is: None longest border of bacab is: b Answers 7
This simple solution with a single loop works just fine:
function findLongestBorder($s){ $a = 0; $b = 1; $n = strlen($s); while($b<$n){ if($s[$a]==$s[$b]){ $a++; }else{ $b-= $a; $a = 0; } $b++; } return substr($s,0,$a); } Example:
echo findLongestBorder("abacab")."\n"; echo findLongestBorder("ababab")."\n"; echo findLongestBorder("abcde hgrab abcde")."\n"; echo findLongestBorder("bacab")."\n"; echo findLongestBorder("abacababac")."\n"; Output:
ab abab abcde b abac Answers 8
I've been using a lot of javascript lately so I did it with Javascript:
function findBorder() { var givenString = document.getElementById("string").value; var length = givenString.length; var y = length; var answer; var subS1; var subS2; for (var x = 0; x < length; x++ ){ subS1 = givenString.substring(0, x); subS2 = givenString.substring(y); if(subS2 === subS1){ answer = subS1; } y--; } document.getElementById("answer").innerHTML = answer.toString(); }<h1>put the string in here</h1> <input type="text" id="string" /> <button id="goButton" onclick="findBorder()">GO</button> <h3 id="answer"></h3>Answers 9
If you are talking about character arrays, I think you want the following. This is based on the border being the first and last character of a string. Your examples aren't clear as to what a border is. You need to more clearly define what a border is.
x = abcde border = { x[0], x[length(x)-1) } and if you need length
length(z) { return sizeof(z) / (sizeof(z[0]) 
0 comments:
Post a Comment