Как сравнить два массива символов и увидеть местоположение?

Question

Пример: первая последовательность (A, B, C, D) вторая последовательность (X, A, Z, A, B, C, D, E, A)

Первая последовательность содержится ввторая последовательность из позиции 4, потому что буквы A, B, C, D появляются в том же порядке, что и первая последовательность

char[] firstSequence = new char[] { 'A', 'B', 'C', 'D'};
char[] secondSequence = new char[] {'X','A','Z','A','B','C','D','E','A'}

Answer 1

Примечание;на момент написания этого ответа не было ясно, что обсуждаемые последовательности являются массивами char. Этот ответ дает более общий совет для коллекций строк или сложных типов. Для массивов char возможна конкретная оптимизация отсутствия строкового разделителя или использования строкового конструктора, который принимает массив char;другие ответы упоминают об этом, поэтому я не буду повторять это здесь

---

Не совсем уверен, как вы храните свои последовательности, но, надеюсь, они перечисляются в этом случае:

string.Join(",", haystackCollection).Contains(string.Join(",", needleCollection));

Я использовал запятую в качестве разделителя, но вы должны использовать символ, который никогда не встречается в реальных коллекциях

Более полный пример:

var haystackCollection = "XAZABCDEA".ToCharArray();
var needleCollection = "ABCD".ToCharArray();

bool result = string.Join(",", haystackCollection).Contains(string.Join(",", needleCollection));

Это надежно, только если ваши коллекции представляют собой строки одинаковой длины,Становится ненадежным, если в стоге сена могут содержаться строки различной длины, потому что в стоге сена {"AB","AC"} нет иглы {"B","A"}, но этот метод сообщает, что это так.

Вы можете сделать это лучше, поместив разделители в начале и конце каждого объединения строк, например:

string s = ",";
(s+string.Join(s, haystackCollection)+s).Contains(s+string.Join(",", needleCollection)+s);

Но в этот момент может быть лучше полностью переключить метод. Также, если вы хотите узнать индекс, он встречается немного сложнее, используя этот метод соединения строк, потому что вам придется использовать IndexOf, а затем многократно вычитать длины каждого элемента плюс разделитель, чтобы вернуться к индексу. Возможно, вам лучше использовать петли:

int idx = 0;
while(idx < haystack.Length){
  if(haystack[idx] == needle[0]){
    int i = 1;
    while(haystack[idx+i] == needle[i] && i<needle.Length)
      i++;
    if(i == needle.Length)
      return idx; // you found the start of the needle
  }
  idx++;
}

В этом последнем методе мы начинаем просматривать стог сена, пытаясь найти первый элемент иглы. Если мы найдем его, мы начнем цикл, который проверяет остальную часть иглы. Эта петля только удерживает гонг, пока он находит записи иголки в стоге сена. Если цикл останавливается досрочно, то индексная переменная i не будет увеличиваться вплоть до длины массива игл, поэтому мы можем сделать вывод, что если переменная i действительно равна длине иглы,игла была найдена в позиции idx в стоге сена

Чтобы этот метод сработал, вам действительно нужно, чтобы ваши коллекции были индексируемыми с помощью Integer, а не просто перечислимыми, если только вы не хотите получить более запутанную. Помните, что если вы используете List вместо Array, то это Count, а не Length

Answer 2

Конвертируйте firstSequence и secondSequence в строку, а затем используйте .Contains().

//Inputs
char[] firstSequence = new char[] { 'A', 'B', 'C', 'D'};
char[] secondSequence = new char[] {'X','A','Z','A','B','C','D','E','A'}

//Convert char array to string
string firstString = new string(firstSequence);
string secondString = new string(secondSequence);

//Use .Contains() to check string availability
bool isExist = secondString.Contains(firstString);

//Print message on console
Console.WriteLine(isExist ? "Sequence Exist" : "Sequence Not Exist");

//This will give you staring index of first string in second string i.e 3
//Next four will be your indexes that are 3, 4, 5, 6
if(isExist)
   {
       int startIndex = secondString.IndexOf(firstString);
       Console.WriteLine(string.Join(", ", Enumerable.Range(startIndex , firstString.Length)));
   }

Результат:

Sequence Exist
3, 4, 5, 6

.NetFiddle

Answer 3

Мне не ясен ваш вопрос, но если вы хотите найти позицию строки в другой строке, вы можете использовать это:

  char[] firstSequence = new char[] { 'A', 'B', 'C', 'D'};
  char[] secondSequence = new char[] {'X','A','Z','A','B','C','D','E','A'}
  var firstString = new string(firstSequence);
  var secondString = new string(secondSequence);
  var positionIndex = secondString.IndexOf(fisrtString);

Answer 4

Если вы хотите просто проверить, что firstSequence элементы появляются где-то в пределах secondSequence в том же порядке, что и в firstSequence, например,

 {A, X, A, B, P, Q, D, A, C, D}
        ^  ^              ^  ^  
        A  B              C  D      

Вы можете попробовать Linq Aggregate: имея элемент a и index в firstSequence, который мы хотим сопоставить, мы можем вычислить index, который мы хотим сопоставить со следующим элементом в secondSequence

Код:

using System.Linq;

... 

bool contains = secondSequence.Aggregate(0, 
   (index, a) => (index >= firstSequence.Length) || (firstSequence[index] != a)
     ? index                               // match completed or nothing to macth 
     : index + 1) >= firstSequence.Length; // match next item

Та же идея, но другая Aggregate, если все firstSequence должны отображаться без перерывов:

 {A, X, A, B, C, D, P, Q}
        ^  ^  ^  ^  
        A  B  C  D  

Код:

using System.Linq;

... 

bool contains = secondSequence
  .Aggregate(0, (index, a) =>
       index >= firstSequence.Length ? index // match found, do nothing
     : firstSequence[index] == a ? index + 1 // can we match next item?
     : firstSequence[0] == a ? 1             // restart and match the 1st item
     : 0)                                    // restart
    >= firstSequence.Length;                 // Have we match all items?