Swift implementation of the longest common subsequence (LCS) algorithm.

Related tags

Algorithm swift diff algorithm lcs
Overview

SwiftLCS

Build Status Carthage compatible Pods Pod platforms

SwitLCS provides an extension of Collection that finds the indexes of the longest common subsequence with another collection.

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

The project is based on the Objective-C implementation of NSArray+LongestCommonSubsequence.

📦 Installation

CocoaPods

CocoaPods is the dependency manager for Swift and Objective-C Cocoa projects. It has over ten thousand libraries and can help you scale your projects elegantly.

Add this to your Podfile:

use_frameworks!

pod 'SwiftLCS'

Carthage

Carthage builds your dependencies and provides you with binary frameworks, but you retain full control over your project structure and setup.

Add this to your Cartfile:

github "Frugghi/SwiftLCS"

Swift Package Manager

The Swift Package Manager is a tool for managing the distribution of Swift code. It’s integrated with the Swift build system to automate the process of downloading, compiling, and linking dependencies.

Add SwiftLCS to your Package.swift dependencies:

import PackageDescription

let package = Package(
    dependencies: [
        .Package(url: "https://github.com/Frugghi/SwiftLCS.git", majorVersion: 1, minor: 3)
    ]
)

Manual

Include SwiftLCS.swift into your project.

📖 Documentation

The API documentation is available here.

💻 Usage

Import the framework:

import SwiftLCS

String

let x = "abracadabra"
let y = "yabbadabbadoo"

let z = x.longestCommonSubsequence(y) // abadaba

Array

let x = [1, 2, 3, 4, 5, 6, 7]
let y = [8, 9, 2, 10, 4, 11, 6, 12]

let z = x.longestCommonSubsequence(y) // [2, 4, 6]

Indexes

let x = [1, 2, 3, 4, 5, 6, 7]
let y = [8, 9, 2, 10, 4, 11, 6, 12]

let diff = x.diff(y)
// diff.commonIndexes: [1, 3, 5]
// diff.addedIndexes: [0, 1, 3, 5, 7]
// diff.removedIndexes: [0, 2, 4, 6]

⚠️ Objective-C

Object comparison of Objective-C objects is done through the isEquals: method, so be sure that the implementations is correct otherwise SwiftLCS will not return the correct indexes.

📄 License LICENSE

SwiftLCS is released under the MIT license. See LICENSE for details.

You might also like...
swift-algorithm 눈물이 차올라서 고갤 들어..
swift-algorithm 눈물이 차올라서 고갤 들어..

swift-algorithm 눈물이 차올라서 고갤 들어.. 알고리즘 정리 Union Find Dynamic Programming 자주 사용되는 문법 1. for문 거꾸로 돌리기 0...n의 반대 for i in stride(from: n, to: 0, by: -1) {

윤예지 6 Nov 8, 2022
💻 A fast and flexible O(n) difference algorithm framework for Swift collection.
💻 A fast and flexible O(n) difference algorithm framework for Swift collection.

A fast and flexible O(n) difference algorithm framework for Swift collection. The algorithm is optimized based on the Paul Heckel's algorithm. Made wi

Ryo Aoyama 3.3k Jan 4, 2023
The Binary Search Algorithm in Swift 🤯 👨🏻‍💻
The Binary Search Algorithm in Swift 🤯 👨🏻‍💻

Binary Search in Swift Binary search is a simple algorithm that lets you search an array for a specific value. It’s trivial to implement in Swift, whi

Sergey Lukaschuk 1 Nov 16, 2021
Swift package wrapping the OpenWall BCrypt hashing algorithm

SwiftBCrypt A simple Swift Package wrapping the OpenWall BCrypt hashing algorithm. Generate Salt let bcryptSalt = try BCRypt.makeSalt() Hash Phrases

Tanner Silva 1 Jul 8, 2022
Debit/Credit card validation port of the Luhn Algorithm in Swift

SwiftLuhn Warning! This repository is no longer maintained. This is a port of the Luhn Algorithm, generally used for validating debit/credit card deta

Max Kramer 135 Sep 9, 2022
Simple and secure hashing in Swift with the SipHash algorithm

SipHash ⚠️ WARNING This package has been obsoleted by the Hasher type and the Hashable.hash(into:) requirement introduced in Swift 4.2. Using this pac

null 262 Dec 19, 2022
A mosaic collection view layout inspired by Lightbox's Algorithm, written in Swift 🔶
A mosaic collection view layout inspired by Lightbox's Algorithm, written in Swift 🔶

TRMosaicLayout A mosaic collection view layout inspired by Lightbox's Algorithm. This is a swift implementation/extension of @fmitech's FMMosaicLayout

Vincent Le 252 Nov 23, 2022
Algorithm is a library of tools that is used to create intelligent applications.
Algorithm is a library of tools that is used to create intelligent applications.

Welcome to Algorithm Algorithm is a library of tools that is used to create intelligent applications. Features Probability Tools Expected Value Progra

Cosmicmind 821 Jan 9, 2023
Differific is a diffing tool that helps you compare Hashable objects using the Paul Heckel's diffing algorithm
Differific is a diffing tool that helps you compare Hashable objects using the Paul Heckel's diffing algorithm

Differific is a diffing tool that helps you compare Hashable objects using the Paul Heckel's diffing algorithm. Creating a chan

Christoffer Winterkvist 127 Jun 3, 2022
Algorithm is a library of tools that is used to create intelligent applications.
Algorithm is a library of tools that is used to create intelligent applications.

Welcome to Algorithm Algorithm is a library of tools that is used to create intelligent applications. Features Probability Tools Expected Value Progra

Cosmicmind 820 Dec 9, 2022
Simple macOS app that applies Apple's Person Segmentation algorithm to a video.
Simple macOS app that applies Apple's Person Segmentation algorithm to a video.

Simple macOS app that applies Apple's Person Segmentation algorithm to a video.

Fabio 5 Dec 9, 2022
Luhn Credit Card Validation Algorithm

Luhn Algorithm This is a port of the Luhn Algorithm, generally used for validating Credit Card details, to Objective-C (iOS). Swift port can be found

Max Kramer 127 Nov 27, 2022
A lightweight stochastic optimizer based on slime mold (Slime Mold Algorithm)
A lightweight stochastic optimizer based on slime mold (Slime Mold Algorithm)

Slime This is a Swift implementation of a Slime Mold Algorithm - a stochastic optimizer - generally based on this paper The only dependency required b

Ethan J 4 Aug 6, 2022
Luhn Credit Card Validation Algorithm

Luhn Algorithm This is a port of the Luhn Algorithm, generally used for validating Credit Card details, to Objective-C (iOS). Swift port can be found

Max Kramer 127 Nov 27, 2022
Sweet-swift - Make Swift Sweet by Gracefully Introducing Syntactic Sugar, Helper Functions and Common Utilities

Sweet Swift Make Swift Sweet by Gracefully Introducing Syntactic Sugar, Helper F

Yanzhan Yang 2 Feb 6, 2022
A wrapper for Apple's Common Crypto library written in Swift.

IDZSwiftCommonCrypto A Swift wrapper for Apple's CommonCrypto library. IDZSwiftCommonCrypto works with both CocoaPods and Cathage. For more details on

idz 472 Dec 12, 2022
VectorMath is a Swift library for Mac and iOS that implements common 2D and 3D vector and matrix functions

Purpose VectorMath is a Swift library for Mac and iOS that implements common 2D and 3D vector and matrix functions, useful for games or vector-based g

Nick Lockwood 341 Dec 31, 2022
Postal is a swift framework providing simple access to common email providers.
Postal is a swift framework providing simple access to common email providers.

Postal is a swift framework providing simple access to common email providers. Example Connect let postal = Postal(configuration: .icloud(login: "myem

Snips 644 Dec 23, 2022
A wrapper for Apple's Common Crypto library written in Swift.

IDZSwiftCommonCrypto A Swift wrapper for Apple's CommonCrypto library. IDZSwiftCommonCrypto works with both CocoaPods and Cathage. For more details on

idz 472 Dec 12, 2022
Comments
  • Does Not Recognize Common Indexes For PFObject

    Does Not Recognize Common Indexes For PFObject

    For some reason SwiftLCS does not recognize the two collections as containing common indexes. The two arrays being compared are exactly the same, but SwiftLCS removes all indexes and adds them back instead of simply recognizing that they are common indexes.

    I essentially have a query that pulls all data, and I have SwiftLCS compare the cached data array to the new, in-coming data array.

    opened by ZacharyKhan 5
  • Compiler warning in Xcode 9 GM with Swift 3.2 project

    Compiler warning in Xcode 9 GM with Swift 3.2 project

    SwiftLCS.swift line 116: Conditional downcast from 'Self.Element?' to 'Self.Element' does nothing

    It's relating to this downcast: while let lhs = entry.0 as? Iterator.Element,

    opened by ghowen 4
  • Crash when the length is a bit long

    Crash when the length is a bit long

    Whenever the length of the text is a bit long (about 510 characters) the algorithm crashes in the following function:

    and this line: else if table[i][j] == table[i][j-1]

    /// Walks back through the generated table to generate the diff. fileprivate static func diffFromIndices(_ table: [[Int]], _ x: [Element], _ y: [Element], _ i: Int, _ j: Int) -> Diff {

        if i == 0 && j == 0 {
        return Diff<Element>(results: [])
    } else if i == 0 {
        return diffFromIndices(table, x, y, i, j-1) + DiffStep.insert(j-1, y[j-1])
    } else if j == 0 {
        return diffFromIndices(table, x, y, i - 1, j) + DiffStep.delete(i-1, x[i-1])
    } else if table[i][j] == table[i][j-1] {
        return diffFromIndices(table, x, y, i, j-1) + DiffStep.insert(j-1, y[j-1])
    } else if table[i][j] == table[i-1][j] {
        return diffFromIndices(table, x, y, i - 1, j) + DiffStep.delete(i-1, x[i-1])
    } else {
        return diffFromIndices(table, x, y, i-1, j-1)
    }

}
    opened by alirezadavoodi 2
  • wrong commonIndexes

    wrong commonIndexes 

    let first = [0,1,1,2,3]
let second = [0,1,2,3] 
let diff = first.diff(second)

print("commonIndexes: \(diff.commonIndexes)")

    result in commonIndexes: [0, 1, 2, 3, 4]

    expect: [0, 1, 3, 4] or [0, 2, 3, 4]

    Maybe caused by wrong endIndex in prefix func

    func prefix(_ otherCollection: Self, count: Int, suffix: Int, by areEquivalent: (Element, Element) -> Bool) -> (Int, [Index]) {
        ...
        let endIndex = self.index(self.startIndex, offsetBy: count - suffix)
       let endIndex = self.index(self.startIndex, offsetBy: count - suffix - 1) // maybe???
       ...
    }
    opened by DamonChen117 0
Releases(1.3.5)

  • 1.3.5(Aug 11, 2019)

  • 1.3.4(Apr 10, 2019)

  • 1.3.3(Jun 15, 2018)

    Breaking
    • Must be compiled with Xcode 9.4 or higher and Swift 4.1.
    Enhancements
    • Support for Xcode 9.4.
    • Performance improvements.
    Bug Fixes
    • None.
    Source code(tar.gz)
    Source code(zip)

  • 1.3.2(Feb 27, 2018)

  • 1.3.1(Feb 16, 2018)

  • 1.3.0(Dec 1, 2017)

    Breaking
    • Must be compiled with Xcode 9.1 and Swift 4, use 1.1.1 if you are compiling with Swift 3 or 1.2.0 with Xcode 9.
    Enhancements
    • Support for Xcode 9.1.
    Bug Fixes
    • None.
    Source code(tar.gz)
    Source code(zip)

  • 1.2.0(Sep 17, 2017)

    Breaking
    • Must be compiled with Xcode 9 and Swift 4, use 1.1.1 if you are compiling with Swift 3.
    Enhancements
    • Support for Swift 4.
    Bug Fixes
    • None.
    Source code(tar.gz)
    Source code(zip)

  • 1.1.1(Mar 24, 2017)

  • 1.1.0(Sep 18, 2016)

  • 1.0.1(Apr 26, 2016)

  • 1.0(Oct 19, 2015)

    CollectionType extension:

    An extension of CollectionType, which calculates the diff between two collections.

    • diff() returns the diff between two collections.

    RangeReplaceableCollectionType extension:

    An extension of RangeReplaceableCollectionType, which calculates the longest common subsequence between two collections.

    • longestCommonSubsequence() returns the longest common subsequence between two collections.

    String extension:

    An extension of String, which calculates the longest common subsequence between two strings.

    • longestCommonSubsequence() returns the longest common subsequence between two strings.

    Diff struct:

    A generic struct that represents a diff between two collections.

    Source code(tar.gz)
    Source code(zip)
Owner
Tommaso Madonia
iOS Developer @ SwiftKey
Tommaso Madonia
GitHub
swift-algorithm 눈물이 차올라서 고갤 들어..

swift-algorithm 눈물이 차올라서 고갤 들어.. 알고리즘 정리 Union Find Dynamic Programming 자주 사용되는 문법 1. for문 거꾸로 돌리기 0...n의 반대 for i in stride(from: n, to: 0, by: -1) {

윤예지 6 Nov 8, 2022
Algorithm is a library of tools that is used to create intelligent applications.

Welcome to Algorithm Algorithm is a library of tools that is used to create intelligent applications. Features Probability Tools Expected Value Progra

Cosmicmind 821 Jan 9, 2023
An implementation of HAMT data-structure in Swift

HAMT (for Swift) An implementation of HAMT(Hash Array Mapped Trie, Bagwell) in Swift. Eonil, May 2019. Getting Started Use HAMT type. This type provid

Eonil 47 Jul 22, 2022
Fast sorted collections for Swift using in-memory B-trees

Fast Sorted Collections for Swift Using In-Memory B-Trees Overview Reference Documentation Optimizing Collections: The Book What Are B-Trees? Why In-M

null 1.3k Dec 20, 2022
Algorithms and data structures in Swift, with explanations!

Welcome to the Swift Algorithm Club! Here you'll find implementations of popular algorithms and data structures in everyone's favorite new language Sw

raywenderlich 27.2k Dec 30, 2022
AssignmentChalkboard - A simple assignment made in Swift

AssignmentChalkboard This is a simple assignment that i made in Swift

Angelos Staboulis 0 Jan 29, 2022
Simplex-Swift - A basic implementation of the Simplex algorithm, written in Swift

Simplex-Swift - A basic implementation of the Simplex algorithm, written in Swift

Evgeny Seliverstov 5 Dec 20, 2022
Swift-cuckoo-collections - Cross-platform Swift dictionaries & sets that use a cuckoo hashing algorithm

CuckooCollections A Swift package for open-addressed sets and dictionaries that

Christopher Richez 0 Aug 2, 2022
Simple and secure hashing in Swift with the SipHash algorithm

SipHash ⚠️ WARNING This package has been obsoleted by the Hasher type and the Hashable.hash(into:) requirement introduced in Swift 4.2. Using this pac

null 262 Dec 19, 2022
💻 A fast and flexible O(n) difference algorithm framework for Swift collection.

A fast and flexible O(n) difference algorithm framework for Swift collection. The algorithm is optimized based on the Paul Heckel's algorithm. Made wi

Ryo Aoyama 3.3k Jan 4, 2023