Нахождение самой длинной границы строки

Question

Во-первых, позвольте мне сказать вам, что такое граница строки ,

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

Граница строки - это подстрока, которая является как правильным префиксом, так и надлежащим суффиксомстрока - «правильная» означает, что вся строка не считается подстрокой.Самая длинная граница x - «ab».Самая длинная граница y - это "abab" (префикс и суффикс могут перекрываться).

Другой пример:
В строке " abcde hgrab abcde ", тогда" abcde "является как префиксом, так и суффиксом.Таким образом, это также самая длинная граница строки выше.

Как мне найти самую длинную границу строки?

Answer 1

Нахождение "границы строки" - это то, что делает префиксная функция (также известная как функция отказа) алгоритма Кнута-Морриса-Пратта.Реализация на c ++ (немного измененная версия , этот код ):

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 версия: http://ideone.com/hTW8FL

Сложность этого алгоритма O(n).

Answer 2

Вот реализация Java, основанная на предположении, что границы - это правильные подстроки. (В противном случае самая длинная граница - это просто длина строки.)

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

Это можно было бы немного оптимизировать, начав с массива символов строки, а затем сравнив отдельные символы, но идея алгоритма яснее, чем я его написал.

Answer 3

Вот решение JS с комментарием, в котором используется префиксная функция, о которой DAIe упомянул :

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

Возвращает самую длинную границу каждого префикса в строке (это намного больше, чем запрашивается, но это происходит за линейное время). Таким образом, чтобы получить длину самой длинной границы в полной строке:

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

Еще один отличный ресурс для понимания того, как это работает, - это видео (и то, что перед ним) на Coursera.

Answer 4

В последнее время я много использую javascript, поэтому я сделал это с помощью 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 5

Это простое решение с одним циклом прекрасно работает:

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

Пример:

echo findLongestBorder("abacab")."\n";
echo findLongestBorder("ababab")."\n";
echo findLongestBorder("abcde hgrab abcde")."\n";
echo findLongestBorder("bacab")."\n";
echo findLongestBorder("abacababac")."\n";

Выход:

ab
abab
abcde
b
abac

См. https://eval.in/812640

Answer 6

Я принял решение, используя Python3 (работает также с Python2), используя Counter из collections модуля и max().

Вот мое решение:

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

Вывод:

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 7

Чтобы получить длину самой длинной границы, сделайте следующее:

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

Чтобы получить самую длинную границу, это:

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

Answer 8

Реализация на Perl, с использованием совпадения с регулярным выражением

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

Эта программа получает стандартный ввод в виде строки и находит шаблон.

^ - 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.

Answer 9

Вот код реализации в c, чтобы найти самую длинную границу строки

#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, которая находит максимальную ширину и шаблон границы из строки.*

}

Вывод программы, как показано ниже: // Когда ввод abcdefabcanabcabccabcdef

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

Answer 10

Если вы говорите о массивах символов, я думаю, вы хотите следующее. Это основано на том, что граница является первым и последним символом строки. Ваши примеры не ясно, что такое граница. Вам нужно более четко определить, что такое граница.

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

и если вам нужна длина

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