Найти небольшой массив символов в большой массив символов C#

Question

Скажем, у меня есть большой массив символов с несколькими тысячами элементов:

char[] mobyDick = "..." таким образом, что mobyDick.Length = 2000.

Я хочу, чтобы выяснить, если определенный массив символов существует в этом массиве в таком порядке, и где * это. (Update:. Я на самом деле просто нужно знать, если это после определенного индекса в основном массиве)

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

Вот тот, который использует лямбда, чтобы найти все действительные «начальные точки» для этой категории.

//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 2

Как насчет цикла for для поиска первого символа тестового примера в большом массиве вначале, а затем сравнения последовательных символов в вашем тестовом массиве с последовательными членами большого массива?

Answer 3

Дайте этому попытку:

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 4

Используйте это:

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

LINQ - Set Operators

Answer 5

Я бы попробовать этот метод расширения:

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 6

Это выглядело как интересная проблема, так что мне пришлось пойти на создание метода расширения ...

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 7

Для справки еще одно решение, использующее общие методы расширения. Он работает для любого типа массива, который реализует 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; 
    } 
}