在string中搜索多个字符串

Question

在给定的字符串中,很容易搜索第一次出现的子字符串,如下所示:

int position = "01234".IndexOf ("23"); // returns 2

我想搜索多个可能的字符串中的任何一个的第一次出现:

var options = new [] {"77", "34", "12"};
int position = "01234".ImaginaryIndexOf (options); // should return 1

这样的函数似乎不存在于.NET框架中.我错过了吗？

编辑:为了澄清,我正在寻找一种适用于大输入和不均匀分布选项的方法.想象一下类似的东西

var options = new [] {"x", "y"};
new String ('x', 1000*1000).IndexOf (options)

Answer 1

据我所知，没有内置方法..

但为了做到这一点，您可以迭代所有options并为每个计算IndexOf. 然后检索未找到的最小值-1（“未找到”）：

int position = options.Select(o => "01234".IndexOf(o))
                      .OrderBy(i =>i).FirstOrDefault(i=> i != -1);

或者代替排序（即O(nlogn)）找到最小值（O(n)）：

int position = options.Select(o => "01234".IndexOf(o))
                      .Where(i => i != -1).DefaultIfEmpty(-1).Min();

至于编辑，您可以考虑构建后缀树数组- 该数组包含 m 个项目，其中 m 是单词第一个字母的不同数量options。作为一般示例：

如果选项是："some", "word", "something", "other"那么你会构造：

    0        1        2...
 +-----------------------+
 |  s    |   w    |   o  |
 +- | ------ | ------ | -+
    o        o        t
    |        |        |
    m        r        h
    |        |        |
    e        d        e
   / \       |        |
  $   t      r        $
      |      |
      ...    $

然后迭代字符串并检查每个字母是否在数组中。如果没有继续下一步。如果是，那么您可以加深嵌套树并检查字符串的下一个字母与树中的下一层相比。如果在主字符串的末尾您还没有到达任何一个，那么文本中就$没有任何项目。options当然，您可以将数组作为 aHashSet<T>来改进对单词首字母的搜索。