Longest Common Subsequence (Performance version)

kata programming

مساله:

از ویکی پدیا

طولانی ترین مشکل رایج زیر دنباله ها(LCS) مشکل یافتن طولانی ترین زیر دنباله مشترک بین همه دنباله ها در مجموعه ای از دنباله ها است.

این مشکلات یافتن زیر رشته های متداول تفاوت دارد: بر خلاف زیر رشته ها ، زیر دنباله ها نیازی به اشغال موقعیت های متوالی در دنباله های اصلی ندارند.

وظیفه:

یک تابع lcs بنویسید که دو رشته را بپذیرد و طولانی ترین زیردنباله مشترک آنها را به عنوان یک رشته برگرداند. سرعت اهمیت دارد.

مثال ها:

lcs( "abcdef", "abc" ) => "abc"
lcs( "abcdef", "acf" ) => "acf"
lcs( "132535365", "123456789" ) => "12356"
lcs( "abcdefghijklmnopq", "apcdefghijklmnobq" ) => "acdefghijklmnoq"

تست:

این یک نسخه عملکردی از کاتای xDranik با همین نام است. با این حال ، این کاتا آزمایشات کامل تر و سنگین تری دارد. آزمونهای تصادفی میانی دارای آرگومانهای رشته ای 20 کاراکتر هستند. آزمایشات تصادفی سخت 40 کاراکتر ؛ افراطی 60 کاراکتر ( کاراکتر ها از بین 36 کاراکتر مختلف انتخاب می شوند).

نکته ها:

زیر دنباله های “abc” عبارتند از “”, “a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”

“” یک زیر دنباله درست در این کاتا است و می تواند یک جواب باشد. همه ورودی ها درست هستند.

دو رشته می تواند بیش از یک طولانی زیردنباله مشترک داشته باشد. زمانی که این اتفاق افتاد، تمام زیر دنباله ها را برگردانید.

lcs( string0, string1 ) === lcs( string1, string0 )

ویکی پدیا مقاله ای در این رابطه دارد که می تواند مفید باشد.


Description:

Longest Common Subsequence (Performance version)

from Wikipedia:
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences.
It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Task

Write a function lcs that accepts two strings and returns their longest common subsequence as a string. Performance matters.

Examples

lcs( "abcdef", "abc" ) => "abc"
lcs( "abcdef", "acf" ) => "acf"
lcs( "132535365", "123456789" ) => "12356"
lcs( "abcdefghijklmnopq", "apcdefghijklmnobq" ) => "acdefghijklmnoq"

Testing

This is a performance version of xDranik‘s kata of the same name.
This kata, however, has much more full and heavy testing. Intermediate random tests have string arguments of 20 characters; hard random tests 40 characters; extreme 60 characters (characters are chosen out of 36 different ones).

Notes

The subsequences of "abc" are "", "a", "b", "c", "ab", "ac", "bc", "abc".
"" is a valid subsequence in this kata, and a possible return value.
All inputs will be valid.
Two strings may have more than one longest common subsequence. When this occurs, return any of them.

lcs( string0, string1 ) === lcs( string1, string0 )

Wikipedia has an article that may be helpful.


class Lcs {

public static String lcs(String x, String y) {

    if (x.length() == 0 || y.length() == 0 || x == null || y == null)
        return "";

    String MaxResult = "";
    String result = "";
    for (int i = 0; i < x.length(); i++) {

        String currRes = x.substring(i, i+1);
        int posRes = y.indexOf(currRes);
        if (posRes >= 0) {
          result = currRes+lcs(x.substring(i+1),y.substring(posRes+1));
        }
        if (result.length() > MaxResult.length()) {MaxResult = result;}
      }

      return MaxResult;
  }
  
  

}
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

public class Lcs {

    static String lcs(String a, String b) {
        List<String> lower = a.length() > b.length() ? Arrays.asList(b.split("")) : Arrays.asList(a.split(""));
        List<String> bigger = a.length() <= b.length() ? Arrays.asList(b.split("")) : Arrays.asList(a.split(""));
        return lcs_recursion(lower, bigger);// do it!
    }

    public static String lcs_recursion(List<String> lower, List<String> bigger) {
        AtomicInteger lowerIndex = new AtomicInteger(Integer.MAX_VALUE);
        final String[] result = {""};
        lower.forEach(item -> {
            if (bigger.contains(item) && bigger.indexOf(item)< lowerIndex.get()) {
                lowerIndex.set(bigger.indexOf(item));
                String res = lcs_recursion(lower.subList(lower.indexOf(item)+1, lower.size()), bigger.subList(bigger.indexOf(item)+1, bigger.size()));
                result[0] = res.length() + 1> result[0].length() ? item + res : result[0];
            }
        });
        return result[0];
    }

}
class Lcs {

  static String lcs(String a, String b) {
    char[] X = a.toCharArray();
    char[] Y = b.toCharArray();
    int m = X.length;
    int n = Y.length;
    int L[][] = new int[m + 1][n + 1];

    for ( int i = 0; i <= m; i++ ) {
      for ( int j = 0; j <= n; j++ ) {
        if ( i == 0 || j == 0 ) {
          L[i][j] = 0;
        }
        else if ( X[i - 1] == Y[j - 1] ) {
          L[i][j] = L[i - 1][j - 1] + 1;
        }
        else {
          L[i][j] = Math.max( L[i - 1][j], L[i][j - 1] );
        }
      }
    }

    int index = L[m][n];

    StringBuilder sb = new StringBuilder( index );

    int i = m, j = n;
    while ( i > 0 && j > 0 ) {
      if ( X[i - 1] == Y[j - 1] ) {
        sb.append( X[i - 1] );

        i--;
        j--;
        index--;
      }
      else if ( L[i - 1][j] > L[i][j - 1] ) {
        i--;
      }
      else {
        j--;
      }
    }

    return sb.reverse().toString();
  }

}
class Lcs {

  static String lcs(String a, String b) {
    if(a.length() == 0 || b.length() == 0){
      return "";
    }
    if(a.equals(b)){
      return a;
    }
    
    char[] arrA = a.toCharArray();
    char[] arrB = b.toCharArray();
    
    
    int startIndex = 1;
    int lengthA = arrA.length + 1; // + 1 since the first row and cols = 0 length.
    int lengthB = arrB.length + 1;
    
    int[][] path = new int[lengthA][lengthB];
    // Create "path" that tracks the longest
    // subsequence calculated from each character.
    // The end of the "path" will be the longest 
    // common subsequence length.
    for(int i = startIndex; i < lengthA; i++){
      for(int j = startIndex; j < lengthB; j++){
        if(arrA[i - 1] == arrB[j - 1]){
          // Matching character.
          path[i][j] = path[i - 1][j - 1] + 1;
        } else {
          // Find the longest common subsequence length
          // and continue from that subsequence.
          int left = path[i - 1][j];
          int above = path[i][j - 1];
          path[i][j] = left > above? left:above;
        }
      }
    }
    // From the end of the path, 
    // backtrack and print the longest common subsequence
    return getLcs(path, arrA, arrB, lengthA - 1, lengthB - 1);
  }
  
  private static String getLcs(int[][] path, char[] a, char[] b, int i, int j){
    if(i == 0 || j == 0){
      // Root of subsequence.
      return "";
    }else if(a[i - 1] == b[j - 1]){
      // Matching character, append and move diagonally up.
      return getLcs(path, a, b, i - 1, j - 1) + a[i - 1];
    }else if(path[i][j - 1] > path[i - 1][j]){
      // above has greater length, backtrack to above.
      return getLcs(path, a, b, i, j - 1);
    }else{
      // backtrack to the left.
      return getLcs(path, a, b, i - 1, j);
    }
  }
  
}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *