.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 string
s 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)}");