String.IndexOfAny(string, string[]) (lowest position for group of needles in haystack)

Question

This is a follow-up to this question with bug fixes, question and code improvements from @dfhwze, @PieterWitvoet, @HenrikHansen, @t3chb0t. I am still hoping for an improved approach or algorithm rather than micro-optimizations to the code.

.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.

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) => s.IndexOfAny3(StringComparison.Ordinal, targets);
public static int IndexOfAny2(this string s, StringComparison sc, params string[] targets) {
    if (targets == null || targets.Length == 0)
        return -1;

    int index = s.IndexOf(targets[0], sc);
    var sLen = s.Length;

    for (int j1 = 1; j1 < targets.Length; ++j1) {
        var target = targets[j1];
        var targetIndex = s.IndexOf(target, 0, index >= 0 ? Math.Min(sLen, index + target.Length) : sLen, sc);

        if (targetIndex >= 0 && (index == -1 || targetIndex < index)) {
            index = targetIndex;
            if (index == 0) // once you're at the beginning, can't be any less
                break;
        }
    }

    return index;
}

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($"IndexOfAny1 should be 0: {"abc".IndexOfAny1("c", "abc")}");

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

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

It seems that you've managed to fix the algorithm, so it does what it's supposed to do. But the concept is the same and performance isn't improved.

Still you could use some more descriptive names, and i instead of j1 (why 1?).

You could use foreach (string target in targets) { ... } instead of for (int j1;...) because you don't use the index to anything and the performance for an array is about the same for the two for-concepts.

---

You ask for other algorithm types that improves performance.

One concept for the algorithm - that seems to improve the performance significantly - could be the following:

public static int IndexOfAny(this string text, params string[] targets)
{
  if (string.IsNullOrEmpty(text)) return -1;
  if (targets == null || targets.Length == 0) return -1;

  for (int i = 0; i < text.Length; i++)
  {
    foreach (string target in targets)
    {
      if (i + target.Length <= text.Length && target == text.Substring(i, target.Length))
        return i;
    }
  }

  return -1;
}

---

Another that can improve performance even more is the following written in pseudo code - leaving it as a challenge for you to implement it in C#:

IndexOfAny text targets:
    for i = 0 to len(text)-1:
        skip = len(text)
        foreach target in targets:
            target_can_skip = 0
            for k = 0 to len(target)-1:
                if target[k] <> text[i+k]:
                    target_can_skip = count how many chars that can be skipped in text before target can be a candidate again
                    break
            if k == len(target):
                return i


            skip = min(skip, target_can_skip)

        if skip > 0: 
            i = i + skip - 1

    return -1 // No match found

---

Besides that you may find inspiration here

---

Update according to VisualMelons comments:

The above implemented with string.IndexOf():

public static int IndexOfAny1(this string text, params string[] targets)
{
  if (string.IsNullOrEmpty(text)) return -1;
  if (targets == null || targets.Length == 0) return -1;

  for (int i = 0; i < text.Length; i++)
  {
    foreach (string target in targets)
    {
      if (i + target.Length <= text.Length && text.IndexOf(target, i, target.Length) == i)
        return i;
    }
  }

  return -1;
}

Notice that the count parameter must be at minimum the length of target or else it will not be found.

Test case:

  Stopwatch watch = Stopwatch.StartNew();
  IndexOfAnyDelegate[] funcs = new IndexOfAnyDelegate[]
  {
    Extensions.IndexOfAny,
    //Extensions.IndexOfAny1,
  };

    int sum = 0;

    for (int i = 0; i < 10000; i++)
    {
      foreach (var func in funcs)
      {
        sum += func("foo bar baz", "foo", "barz", "baz", " ");
        sum += func("aabbccddeeffgghh", "bbb", "hh", "aaa", "fg");
        sum += func("abcabc", "c", "abc");
        sum += func("abcabc", "x", "wer");
        sum += func("adfaææwjerqijaæsdklfjaeoirweqærqkljadfaewrwexwer", "xxxxx", "yyyyy", "zzzzz", "Aaaaaa", "x", "wer");

        //Console.WriteLine($"IndexOfAny should be 8: {func("foo bar baz", "barz", "baz", " ", "foo")}");
        //Console.WriteLine($"IndexOfAny should be 0: {func("aabbccddeeffgghh", "bbb", "hh", "aaa", "fg")}");
        //Console.WriteLine($"IndexOfAny should be 0: {func("abcabc", "c", "abc")}");
        //Console.WriteLine($"IndexOfAny should be 0: {func("abcabc", "x", "wer")}");
        //Console.WriteLine(func("adfaææwjerqijaæsdklfjaeoirweqærqkljadfaewrwexwer", "xxxxx", "yyyyy", "zzzzz", "Aaaaaa", "x", "wer"));
        //Console.WriteLine();
      }
    }
    watch.Stop();
    Console.WriteLine(sum);
    Console.WriteLine(watch.ElapsedMilliseconds);

You'll have to comment in/out as needed.

---

Update 2

The performance of the above pseudo code decreases (obviously) when the number of targets increases. So my analysis wasn't quite good enough. To optimize on that problem the below variant maintains an array of the next valid index per target, which minimize the number of targets that should be examined per char in the text string:

public static int IndexOfAny(this string text, params string[] targets)
{
  if (string.IsNullOrEmpty(text)) return -1;
  if (targets == null || targets.Length == 0) return -1;

  // Holds the next valid index in text per parget.
  int[] targetNextIndex = new int[targets.Length];

  for (int i = 0; i < text.Length; i++)
  {
    for (int j = 0; j < targets.Length; j++)
    {
      // If the targets next index isn't i then continue to next target
      if (targetNextIndex[j] > i)
        continue;

      string target = targets[j];
      int k = 0;

      for (; k < target.Length && i + k < text.Length; k++)
      {
        if (target[k] != text[i + k])
        {
          int nextIndex = i + 1;
          // Tries to find the next index in text where the char equals the first char in target.
          while (nextIndex < text.Length && target[0] != text[nextIndex])
          {
            nextIndex++;
          }
          // The next valid index for the target is found, so save it
          targetNextIndex[j] = nextIndex;
          break;
        }
      }

      if (k == target.Length)
      {
        return i;
      }
    }
  }

  return -1;
}