在大型字符数组 C# 中查找小字符数组

Question

>假设我有一个包含数千个项目的大字符数组：

char[] mobyDick = "..."这样mobyDick.Length = 2000。

我想找出该数组中是否按该顺序存在某个字符数组，以及它在哪里*。（更新：我真的只需要知道它是否在主数组中的某个索引之后。

char[] test = {'a','b','c','d'}

我可以做类似的事情

char[] mobyDick = "..."
string mobyString = new string(mobyDick);
if (mobyString.Contains(new string(test)))
{ do stuff}

但这对我的情况来说不是最佳的，因为我正在尝试编写一个必须非常快速地工作的解析器，而且我不想在每个字母左右创建和搜索字符串。

有没有办法（算法或通过一些 .Net 方法）来确定作为字符数组的mobyDick是否包含作为字符数组的abcd？

Answer 1

这看起来是一个有趣的问题，所以我尝试创建一个扩展方法......

 public static class ExtensionMethods
{
    public static int ContainsArray(this char[] arrayToSearchIn, char[] arrayToFind)
    {
        if (arrayToFind.Length == 0)
            return -1;
        int lengthOfArrayToFInd = arrayToFind.Length;
        int lengthOfArrayToSearchIn = arrayToSearchIn.Length;
        for (int i = 0; i < lengthOfArrayToSearchIn; i++)
        {
            if (lengthOfArrayToSearchIn - i < lengthOfArrayToFInd)
                return -1;
            if (arrayToSearchIn[i] != arrayToFind[0])
                continue;
            int arrayToFindCounter = 0;
            bool wasFound = true;
            for (int j = i; j < i + lengthOfArrayToFInd; j++)
            {
                if (arrayToFind[arrayToFindCounter] == arrayToSearchIn[j])
                    arrayToFindCounter++;
                else
                {
                    wasFound = false;
                    break;
                }
            }
            if (wasFound)
                return i;
        }
        return -1;
    }
}

这似乎（对我来说）适用于任何长度的子数组，包括空搜索 - 如果找到（从零开始），则返回第一次出现的位置，否则返回 -1。

示例用法：

 static void Main(string[] args)
    {
        //                        0    1    2    3    4    5    6    7    8    9    0    1    2    3    4    5    6    7    8  
        char[] mobyDick = new[] {'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'd', 'a', 'z', 'y'};
        char[] test = {'a', 'b', 'c', 'd'};
        Console.WriteLine(mobyDick.ContainsArray(test));  // Position 12
        Console.ReadLine();
    }

Answer 2

这是一个使用 lambda 来查找搜索的所有有效"起点"的方法。

//return first index of substring or -1 for not found
int searchForChar(char [] substring, char [] fulltext)
{
    //all of the start points
    var indices = fulltext.Select ((b,i) => b == substring.FirstOrDefault() ? i : -1)
                          .Where(i => i != -1).ToArray();
    //search each start point
    foreach (var index in indices)
    {
        var found = true;
        int count = 0;
        for(int i = index; i < index + substring.Length; i++)
        {   
            found = true;
            if(substring[count++] != fulltext[i])
            {   
                found = false;
                break;
            }   
        }
        if (found) return index;
    }
    return -1;
}

可能，一种更高性能的执行此操作的方法类似于您原始问题中的内容。

int searchForChar(char [] substring, char [] fulltext)
{
    return fulltext.ToString().IndexOf(substring.ToString());
}

Answer 3

我会尝试这种扩展方法：

public static bool ContainsChars(this char[] source, char[] target,out int index)
{
     int targetLength = target.Length - 1;
     int count = 0;
     char currentCharToSearch = target[0];
     for(int i=0; i<source.Length; i++)
     {
          if (source[i] == currentCharToSearch)
          {
              count++;
              if (count == targetLength) 
              {
                  index = i - count + 1;
                  return true;
              }
              else
              {
                  currentCharToSearch = target[count];
              }
           }
           else
           {
               count = 0;
               currentCharToSearch = target[0];
           }
      }
      index = -1;
      return false;
}

用法：

var c1 = new char[] { 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'h', 't' };
var c2 = new char[] { 'c', 'h', 't' };
int index;
var result = c1.ContainsChars(c2,out index); // true index = 6
c2 = new char[] { 'c', 't', 'h' };
var result2 = c1.ContainsChars(c2,out index); // false index = -1

Answer 4

试一试：

private bool Contains(char[] mobyDick, char[] test)
{
    for (int i = 0; i < mobyDick.Length - test.Length + 1; i++)
    {
        bool found = true;
        for (int j = 0; j < test.Length; j++)
        {
            if (mobyDick[i + j] != test[j])
            {
                found = false;
                break;
            }
        }
        if (found) return true;
    }
    return false;
}

Answer 5

for 循环首先搜索大数组中测试用例的第一个字符，然后将测试数组中的连续字符与大数组的连续成员进行比较怎么样？

Answer 6

作为记录，这是使用通用扩展方法的另一种解决方案。它适用于实现 IComparable 的任何阵列类型。

void Main()
{
    var c1 = new char[] { 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'h', 't' };
    var c2 = new char[] { 'c', 'h', 't' };
    if (c1.Contains(c2))
    {
        // do something
    }
    int i = c1.IndexOf(c2);
}
public static class ArrayExtensions
{
    public static bool Contains<T>(this T[] array, T[] subarray) where T : IComparable
    {
        return array.IndexOf(subarray) >= 0;
    }
    public static int IndexOf<T>(this T[] array, T[] subarray) where T : IComparable
    {
        for (int i = 0; i < array.Length - subarray.Length + 1; i++)
        {
            bool found = true;
            for (int j = 0; j < subarray.Length; j++)
            {
                if (array[i + j].CompareTo(subarray[j]) != 0)
                {
                    found = false;
                    break;
                }
            }
            if (found) return i;
        }
        return -1;
    }
}

Answer 7

使用这个：

var search = mobyDick.Intersect(test);
if (search.ToArray().Length > 0)
{
//do something
}

LINQ - 设置运算符