Tìm biên giới dài nhất của một chuỗi

Question

Đầu tiên, hãy để tôi nói cho bạn những border of a string là gì,

let x = "abacab" 
let y = "ababab" 

Biên giới của một chuỗi là một chuỗi con đó là cả một tiền tố phù hợp và hậu tố thích hợp của chuỗi - " đúng "nghĩa là toàn bộ chuỗi không được tính là chuỗi con. Đường viền dài nhất của x là "ab". Đường biên dài nhất của y là "abab" (tiền tố và hậu tố có thể trùng lặp).

Một ví dụ khác:
Trong chuỗi "abcde hgrab abcde", sau đó "abcde" là một tiền tố cũng như hậu tố. Vì vậy, nó cũng là đường viền dài nhất của chuỗi ở trên.

Tôi làm cách nào để tìm đường viền dài nhất của chuỗi?

Answer 1

Nếu bạn đang nói về mảng ký tự, tôi nghĩ bạn muốn như sau. Điều này được dựa trên biên giới là ký tự đầu tiên và cuối cùng của một chuỗi. Ví dụ của bạn không rõ ràng về biên giới là gì. Bạn cần xác định rõ hơn ranh giới là gì.

x = abcde 
border = { x[0], x[length(x)-1) } 

và nếu bạn cần chiều dài

length(z) { 
    return sizeof(z)/(sizeof(z[0]) 

Answer 2

Để có được chiều dài biên giới dài nhất, làm điều này:

def get_border_size(astr): 
    border = 0 
    for i in range(len(astr)): 
     if astr[:i] == astr[-i:]: 
      border = i 
    return border 

Để có biên giới dài nhất bản thân, điều này:

def get_border(astr): 
    border = 0 
    for i in range(len(astr)): 
     if astr[:i] == astr[-i:]: 
      border = astr[:i] 
    return border 

Answer 3

Đây là triển khai Java, dựa trên tiêu thụ rằng các đường biên là thích hợp đế. (Nếu không biên giới dài nhất chỉ đơn giản là chiều dài chuỗi.)

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; 
} 

Điều này có thể được tối ưu hóa một chút bằng cách bắt đầu với mảng nhân vật của chuỗi và sau đó so sánh đặc điểm cá nhân, nhưng ý tưởng đằng sau các thuật toán là rõ ràng hơn con đường tôi đã viết nó.

Answer 4

Tôi đã thực hiện một giải pháp sử dụng Python3 (hoạt động cũng với Python2), sử dụng Counter từ collections mô-đun và max().

Đây là giải pháp của tôi:

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 

Answer 5

Tìm kiếm "border của một chuỗi" là những gì mà prefix function (còn gọi là chức năng thất bại) của Knuth-Morris-Pratt thuật toán. Thực hiện trong C++ (một chút thay đổi phiên bản của 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 phiên bản: http://ideone.com/hTW8FL

Sự phức tạp của thuật toán này là O(n).

Answer 6

Giải pháp này đơn giản với một vòng lặp đơn làm việc tốt:

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); 
} 

Ví dụ:

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 

Xem https://eval.in/812640

Answer 7

cô e là một giải pháp JS với bình luận rằng sử dụng hàm prefix rằng 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; 
} 

Nó trả về chiều dài biên giới dài nhất của tất cả các tiền tố trong một chuỗi (mà là nhiều hơn so với yêu cầu, nhưng nó như vậy trong tuyến tính thời gian). Vì vậy, để có được chiều dài của biên giới dài nhất trong chuỗi đầy đủ:

var string = "ababab"; 
var borderLengthsByPrefix = getPrefixBorders(); // [0,0,1,2,3,4] 
var stringBorderLength = borderLengthsByPrefix[borderLengthsByPrefix.length - 1]; 

Một nguồn lực lớn để hiểu được cách làm việc này là this video (và một trong những trước khi nó) trên Coursera.

Answer 8

Tôi đã sử dụng rất nhiều javascript thời gian gần đây vì vậy tôi đã làm điều đó với 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>

Answer 9

Đây là việc thực hiện mã trong c để tìm ra biên giới dài nhất của chuỗi

#include<stdio.h> 
#include<string.h> 
#include <stdlib.h> 
int main() 
{ 
    char str[]="abcdefabcanabcabccabcdef"; 
    int n,i,j,l,k,count,max=0; 
    l=strlen(str); 

    for(i=0;i<(l/2);i++) 
    { j=l-1-i; 
     k=0; 
     count=0; 
     while(k<=i&&j<l) 
     { 
     if(str[k]==str[j]) 
      count++; 
     k++; 
     j++; 

     } 
    if(count==(k)) 
    { 
     if(isasubstring(str,k,l-(2*(k)))) 
      if(max<count) 
       max=count; 
    } 
} 

return 0; 
} 

FUNCTION: isasubstring tìm chiều rộng tối đa và mẫu đường viền từ chuỗi.

isasubstring(char *a,int s,int n) 
{ 
int i,j; 
char *temp; 
char *pattern=malloc(sizeof(char)*(s+1)); 
char *input =malloc(sizeof(char)*(n+1)); 
memcpy(pattern,a,s); 
pattern[s]='\0'; 
j=0; 
for(i=s;i<=s+n-1;i++) 
{ 
    input[j]=a[i]; 
    j++; 
} 
input[j]='\0'; 
printf("The string between the border :%s\n The longest border is: %s\n",input,pattern); 
temp=strstr(input,pattern); 
if(temp) 
    return 1; 
else 
    return 0; 

}

Đầu ra của chương trình như sau: // Khi đầu vào là abcdefabcanabcabccabcdef

The string between the border :abcanabcabcc 
The longest border is: abcdef 

Answer 10

thực hiện trong Perl, Sử dụng biểu thức trận đấu thường xuyên

use strict; 
use warnings; 
while(<STDIN>) 
{ 
    if (/^([a-zA-z]+).*\1$/) 
    { 
      print "Longest Border : $1\n"; 
    } 
    else 
    { 
      print "No border in the pattern as suffix and prefix\n"; 
    } 
} 

Chương trình này nhận đầu vào tiêu chuẩn dưới dạng chuỗi và tìm mẫu .

^ - beginning of the line 
$ - end of the line 
([a-zA-z]+) - Grouping the pattern which holds in $1 or \1 variable 
.* - Match any characters in between the borders.