查找字符串

Question

的陣列的最長公共子串在我的雨燕3.0的應用程序，我想，以確定最佳的名稱，通過找到6至12字符串的最長公共子事。

例字符串：

ON/OFF office lights 
DIM office lights 
VALUE office lights 
FB office lights 
FB VALUE office lights 

所需的輸出：

office lights 

我已經遇到多個StackOverflow的答案最長子，但一直沒能適應任何的他們對我的需要..

任何幫助將不勝感激！

Answer 1

我轉換爪哇 & C++代碼成夫特3，從GeeksForGeeksLongest Common Subsequence & Longest Common Substring收集。

它的工作原理！

class LongestCommon 
{ 
    // Returns length of LCS for X[0..m-1], Y[0..n-1] 
    private static func lcSubsequence(_ X : String , _ Y : String ) -> String 
    { 
     let m = X.characters.count 
     let n = Y.characters.count 

     var L = Array(repeating: Array(repeating: 0, count: n + 1) , count: m + 1) 
     // Following steps build L[m+1][n+1] in bottom up fashion. Note 
     // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 
     for i in stride(from: 0, through: m, by: 1) 
     { 
      for j in stride(from: 0, through: n, by: 1) 
      { 
       if i == 0 || j == 0 
       { 
        L[i][j] = 0; 
       } 
       else if X[X.index(X.startIndex , offsetBy: (i - 1))] == Y[Y.index(Y.startIndex , offsetBy: (j - 1))] 
       { 
        L[i][j] = L[i-1][j-1] + 1 
       } 
       else 
       { 
        L[i][j] = max(L[i-1][j], L[i][j-1]) 
       } 
      } 

     } 

     // Following code is used to print LCS 
     var index = L[m][n] 
     // Create a character array to store the lcs string 
     var lcs = "" 
     // Start from the right-most-bottom-most corner and 
     // one by one store characters in lcs[] 
     var i = m 
     var j = n 

     while (i > 0 && j > 0) 
     { 
      // If current character in X[] and Y are same, then 
      // current character is part of LCS 
      if X[X.index(X.startIndex , offsetBy: (i - 1))] == Y[Y.index(Y.startIndex , offsetBy: (j - 1))] 
      { 
       lcs.append(X[X.index(X.startIndex , offsetBy: (i - 1))]) 
       i-=1 
       j-=1 
       index-=1 
      } 
      // If not same, then find the larger of two and 
      // go in the direction of larger value 
      else if (L[i-1][j] > L[i][j-1]) 
      { 
       i-=1 
      } 
      else 
      { 
       j-=1 
      } 
     } 

     // return the lcs 
     return String(lcs.characters.reversed()) 
    } 

    // Returns length of LCS for X[0..m-1], Y[0..n-1] 
    private static func lcSubstring(_ X : String , _ Y : String ) -> String 
    { 
     let m = X.characters.count 
     let n = Y.characters.count 

     var L = Array(repeating: Array(repeating: 0, count: n + 1) , count: m + 1) 
     var result : (length : Int, iEnd : Int, jEnd : Int) = (0,0,0) 
     // Following steps build L[m+1][n+1] in bottom up fashion. Note 
     // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 
     for i in stride(from: 0, through: m, by: 1) 
     { 
      for j in stride(from: 0, through: n, by: 1) 
      { 
       if i == 0 || j == 0 
       { 
        L[i][j] = 0; 
       } 
       else if X[X.index(X.startIndex , offsetBy: (i - 1))] == Y[Y.index(Y.startIndex , offsetBy: (j - 1))] 
       { 
        L[i][j] = L[i-1][j-1] + 1 

        if result.0 < L[i][j] 
        { 
         result.length = L[i][j] 
         result.iEnd = i 
         result.jEnd = j 
        } 
       } 
       else 
       { 
        L[i][j] = 0 //max(L[i-1][j], L[i][j-1]) 
       } 
      } 

     } 

     // Following code is used to print LCS 


     let lcs = X.substring(with: X.index(X.startIndex, offsetBy: result.iEnd-result.length)..<X.index(X.startIndex, offsetBy: result.iEnd)) 

     // return the lcs 
     return lcs 
    } 

    // driver program 

    class func subsequenceOf(_ strings : [String]) -> String 
    { 
     var answer = strings[0] // For on string answer is itself 

     for i in stride(from: 1, to: strings.count, by: 1) 
     { 
      answer = lcSubsequence(answer,strings[i]) 
     } 
     return answer 
    } 

    class func substringOf(_ strings : [String]) -> String 
    { 
     var answer = strings[0] // For on string answer is itself 

     for i in stride(from: 1, to: strings.count, by: 1) 
     { 
      answer = lcSubstring(answer,strings[i]) 
     } 
     return answer 
    } 



} 

用法：

let strings = ["ON/OFF office lights", 
         "DIM office lights", 
         "VALUE office lights", 
         "FB office lights", 
         "FB VALUE office lights"] 
print(LongestCommon.subsequenceOf(strings)) 
print(LongestCommon.substringOf(strings))