演算法實現/字串/最長公共字首/字尾子串

此演算法是最長公共子串演算法的特例。字首（或字尾）的特例帶來了顯著的效能提升 - 在我的應用程式中，效能提高了大約兩個數量級。

不幸的是，目前我只提供了 Perl 版本，因為這是我的專案所需的！我希望其他需要此演算法的其他語言的人能夠在這裡記錄他們的實現。

C#

最長公共字首和字尾子串

    public static string LCS_start(string word1, string word2)
    {
      int end1 = word1.Length - 1;
      int end2 = word2.Length - 1;

      int pos = 0;

      while (pos <= end1 && pos <= end2)
      {
        if (word1[pos] != word2[pos])
        {
          pos++;
        }
      }
      return word1.Substring(0,pos);
    }

    public static string LCS_end(string word1, string word2)
    {
      int pos1 = word1.Length - 1;
      int pos2 = word2.Length - 1;

      while (pos1 >= 0 && pos2 >= 0)
      {
        if (word1[pos1] != word2[pos2])
        {
          pos1--;
          pos2--;
        }
      }
      return word1.Substring(pos1 + 1);
    }

Javascript

最長公共字首和字尾子串

function LCS_start( word1,  word2) {

  let end1 = word1.length - 1
  let end2 = word2.length - 1

  let pos = 0

  while (pos <= end1 && pos <= end2){
    if (word1[pos] != word2[pos]) {
       return word1.substring(0,pos)
    } else {
        pos++
    }
  }
}

function LCS_end( word1,  word2) {

  let pos1 = word1.length - 1
  let pos2 = word2.length - 1

  while (pos1 >= 0 && pos2 >= 0){
    if (word1[pos1] != word2[pos2]) {
       return word1.substring(pos1 + 1)
    } else {
        pos1--
        pos2--
    }
  }
}

Perl

最長公共字首子串

sub lcl_substr
{
  my $s1 = shift;
  my $s2 = shift;

  my $end1 = length($s1) - 1;
  my $end2 = length($s2) - 1;

  my $pos = 0;

  while ($pos <= $end1 && $pos <= $end2)
  {
   last if substr($s1, $pos, 1) ne substr($s2, $pos, 1);
   $pos++;
  }

  return substr($s1, 0, $pos);
}

最長公共字尾子串

sub lct_substr
{
  my $s1 = shift;
  my $s2 = shift;

  my $pos1 = length($s1) - 1;
  my $pos2 = length($s2) - 1;

  while ($pos1 >= 0 && $pos2 >= 0)
  {
   last if substr($s1, $pos1, 1) ne substr($s2, $pos2, 1);
   $pos1--;
   $pos2--;
  }

  return substr($s1, $pos1+1);
}

Python

最長公共字首子串

def longest_common_leading_substring(string1, string2):

  common = ''
  for s1, s2 in zip(string1, string2):
    if s1 == s2:
      common += s1
  return common

最長公共字尾子串

def longest_common_trailing_substring(string1, string2):

  common = ''
  for s1, s2 in zip(string1[-1::-1], string2[-1::-1]):
    if s1 == s2:
      common += s1
  return common[-1::-1]