Find first index of entry / start of submatrix in C #

Question

Given two arrays as parameters (x and y) and find the starting index, where is the first occurrence of y in x. I am wondering what will be the easiest or fastest implementation.

Example:

when x = {1,2,4,2,3,4,5,6}
     y =       {2,3}
result
     starting index should be 3

Update: Since my code is incorrect, I removed it from the question.

Answer 1

Here is a simple (but fairly efficient) implementation that finds all the events of the array, not just the first one:

static class ArrayExtensions {

  public static IEnumerable<int> StartingIndex(this int[] x, int[] y) {
    IEnumerable<int> index = Enumerable.Range(0, x.Length - y.Length + 1);
    for (int i = 0; i < y.Length; i++) {
      index = index.Where(n => x[n + i] == y[i]).ToArray();
    }
    return index;
  }

}

Example:

int[] x = { 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4 };
int[] y = { 2, 3 };
foreach (int i in x.StartingIndex(y)) {
  Console.WriteLine(i);
}

Output:

1
5
9

x, y index. , , y. y , index .

Edit:
ToArray , :

index = index.Where(n => x[n + i] == y[i]);

. , , , , . , , :

int index = x.StartingIndex(y).First();

, , , , .

Answer 2

?

    return (from i in Enumerable.Range(0, 1 + x.Length - y.Length)
            where x.Skip(i).Take(y.Length).SequenceEqual(y)
            select (int?)i).FirstOrDefault().GetValueOrDefault(-1);

, ... :

private static bool IsSubArrayEqual(int[] x, int[] y, int start) {
    for (int i = 0; i < y.Length; i++) {
        if (x[start++] != y[i]) return false;
    }
    return true;
}
public static int StartingIndex(this int[] x, int[] y) {
    int max = 1 + x.Length - y.Length;
    for(int i = 0 ; i < max ; i++) {
        if(IsSubArrayEqual(x,y,i)) return i;
    }
    return -1;
}

Answer 3

, , :

public static class ArrayExtensions
{
    private static bool isMatch(int[] x, int[] y, int index)
    {
        for (int j = 0; j < y.Length; ++j)
            if (x[j + index] != y[j]) return false;
        return true;
    }

    public static int IndexOf(this int[] x, int[] y)
    {
        for (int i = 0; i < x.Length - y.Length + 1; ++i)
            if (isMatch(x, y, i)) return i;
        return -1;
    }
}

.

Answer 4

"" " " , , , , .

, . , "" " , ". . "bananananananananananananananana" , "banananananabanananabananabananabanananananbananana...", - , , - O (nm), n m - . O (n + m), .

, ? , , ?

Answer 5

Mark Gravell, ,

private static bool IsSubArrayEqual<T>(T[] source, T[] compare, int start) where T:IEquatable<T>
{
    if (compare.Length > source.Length - start)
    {
        //If the compare string is shorter than the test area it is not a match.
        return false;
    }

    for (int i = 0; i < compare.Length; i++)
    {
        if (source[start++].Equals(compare[i]) == false) return false;
    }
    return true;
}

, Boyer-Moore, .

Answer 6

- , .

public static class ArrayExtensions
{
    public static int StartingIndex(this int[] x, int[] y)
    {
        var xIndex = 0;
        while(xIndex < x.length)
        {
            var found = xIndex;
            var yIndex = 0;
            while(yIndex < y.length && xIndex < x.length && x[xIndex] == y[yIndex])
            {
                xIndex++;
                yIndex++;
            }

            if(yIndex == y.length-1)
            {
                return found;
            }

            xIndex = found + 1;
        }

        return -1;
    }
}

, , , , x = {3, 3, 7}, y = {3, 7}. , , , , , , , . , - , -, .

Answer 7

    //this is the best in C#

    //bool contains(array,subarray)
    //  when find (subarray[0])
    //      while subarray[next] IS OK
    //          subarray.end then Return True
    public static bool ContainSubArray<T>(T[] findIn, out int found_index,
 params T[]toFind)
    {
        found_index = -1;
        if (toFind.Length < findIn.Length)
        {

            int index = 0;
            Func<int, bool> NextOk = (i) =>
                {
                    if(index < findIn.Length-1)
                        return findIn[++index].Equals(toFind[i]);
                    return false;
                };
            //----------
            int n=0;
            for (; index < findIn.Length; index++)
            {
                if (findIn[index].Equals(toFind[0]))
                {
                    found_index=index;n=1;
                    while (n < toFind.Length && NextOk(n))
                        n++;
                }
                if (n == toFind.Length)
                {
                    return true;
                }
            }

        }
        return false;
    }

Answer 8

using System;
using System.Linq;

public class Test
{
    public static void Main()
    {
        int[] x = {1,2,4,2,3,4,5,6};
        int[] y =       {2,3};
        int? index = null;

        for(int i=0; i<x.Length; ++i)
        {
            if (y.SequenceEqual(x.Skip(i).Take(y.Length)))
            {
                index = i;
                break;
            }
        }
        Console.WriteLine($"{index}");
    }
}

3