Best C# implementation of IndexOfAny(string, params string[])

Question

Follow-Up question

.Net provides String.IndexOfAny(string, char[]) but not String.IndexOfAny(string, string[]).

The existing built-in String.IndexOfAny takes an array of char and returns the lowest position of any one char from the array in a passed in string or -1 if none are found. Essentially it is the char equivalent of my naive definition.

My extension takes a string to search s and an array of strings to find targets and returns the lowest position found of any member of targets in s or -1 if none are found.

A naive implementation (using LINQ) isn't particularly efficient:

public static int IndexOfAny1(this string s, params string[] targets) =>
    targets.Select(t => s.IndexOf(t)).Where(p => p >= 0).DefaultIfEmpty(-1).Min();

My improved implementation tracks the current candidate position and restricts future searches to be before that candidate position:

public static int IndexOfAny2(this string s, params string[] targets) {
    int? curAns = null;
    foreach (var target in targets) {
        var posAns = s.IndexOf(target, 0, curAns.HasValue ? curAns.Value + target.Length : s.Length);

        if (posAns >= 0 && (!curAns.HasValue || posAns < curAns)) {
            curAns = posAns;
            if (curAns == 0) // once you're at the beginning, can't be any less
                break;
        }
    }

    return curAns ?? -1;
}

This runs up to two times faster.

Sample code to test the two methods:

Console.WriteLine($"IndexOfAny1 should be 8: {"foo bar baz".IndexOfAny1("barz", "baz")}");
Console.WriteLine($"IndexOfAny1 should be 0: {"aabbccddeeffgghh".IndexOfAny1("bbb", "hh", "aa")}");
Console.WriteLine($"IndexOfAny2 should be 8: {"foo bar baz".IndexOfAny2("barz", "baz")}");
Console.WriteLine($"IndexOfAny2 should be 0: {"aabbccddeeffgghh".IndexOfAny2("bbb", "hh", "aa")}");

Is there a better algorithm or another way to make this faster?

PS Test harness for testing random possibilities:

var r = new Random();

var sb = new StringBuilder();
for (int j1 = 0; j1 < r.Next(80,160); ++j1)
    sb.Append((char)('0'+r.Next(0, 26+52)));
var s = sb.ToString();

var listTargets = new List<string>();
for (int j1 = 0; j1 < r.Next(5, 10); ++j1)
    if (r.NextDouble() < 0.8) {
        var tLen = r.Next(4, Math.Min(s.Length - 4, 10));
        var beginPos = r.Next(0, s.Length - tLen);
        listTargets.Add(s.Substring(beginPos, tLen));
    }
    else {
        sb.Clear();
        for (int j2 = 0; j2 < r.Next(5, 10); ++j2)
            sb.Append((char)('0'+r.Next(0, 26+52)));
        listTargets.Add(sb.ToString());
    }

var targets = listTargets.ToArray();
if (s.IndexOfAny1(targets) != s.IndexOfAny2(targets))
    Console.WriteLine($"Fail on {s} containing {String.Join(",", targets)}");

Answer 1

Review

• Don't use abbreviated variable names s, curAns and posAns; use self describing names: value, index and targetIndex instead.
• The nullable int could be replaced with -1. This reads cleaner and allows you to bypass the final ?? operator in curAns ?? -1.
• You can optimize the count curAns.Value + target.Length with adding -1 because we don't care about finding another match on the currently best found index.
• You should exit early if no targets are specified

Refactored

public static int IndexOfAny2(this string value, params string[] targets)
{
    var index = -1;
    if (targets == null || targets.Length == 0) return index;

    foreach (var target in targets)
    {
        var targetIndex = value.IndexOf(target, 0, 
            index > -1 ? index + target.Length - 1 : value.Length);

        if (targetIndex >= 0 && (index == -1 || targetIndex < index))
        {
            index = targetIndex;
            if (index == 0)
            {
                break;
            }
        }
    }

    return index;
}

Answer 2

• "abc".IndexOfAny2("c", "abc") fails with an ArgumentOutOfRangeException, because IndexOf requires startIndex + count to not exceed the length of the string.
• For a tiny improvement, make curAns a normal integer and initialize it with s.Length. After the necessary changes, you'll end up with fewer checks inside the foreach loop.

Most time is spent in string.IndexOf however, so for more substantial improvements you'll want to investigate more optimized (and more complex) algorithms such as Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick, etc.