listkotlinstring-matching

Do Kotlin's List/Array data structures have a findSublist method analogous to String.indexOf(CharSequence)?


Do Kotlin's List/Array data structures have a findSublist method analogous to String.indexOf(CharSequence), that takes a List/Array/Sequence to match against the list?


Solution

  • While both operations are similar in nature, somehow most languages support it for strings and very few support it for collections. The reason may be that it is uncommon to do this for collections, while it is a very common operation for strings. Also, chars are very easy to compare and we can even do some optimizations by utilizing the fact they can be processed as numbers. Collections require to use equals for all comparisons. I suppose above reasons make it not very practical to include such operation in the stdlib and I believe Kotlin doesn't support it.

    If you look for the most elegant or idiomatic solution, it could be:

    fun <T> List<T>.findSublist(sublist: List<T>) = asSequence()
        .windowed(sublist.size) { it }
        .indexOf(sublist)
    

    It is probably suboptimal for the performance, but mostly because of the overhead of sequences and keeping it object-oriented. Technically, it does a similar thing to a more optimized version where we iterate over indexes manually.

    Please note windowed doesn't actually create a new sublist with each iteration. It uses a sliding window, so with each iteration we get exactly the same object with updated contents. For the same reason we are generally not allowed to pass it anywhere as it holds a temporary snapshot of the data. I believe the above solution is fine, because we use a sequence, so the execution flow alternates between the producer (windowed) and the consumer (indexOf).