检查数组是否是递归的子数组

Question

我需要编写一个方法，它接受两个数组作为参数，如果第二个数组是第一个数组的子数组，则返回true，否则返回false。我只需要使用没有循环的递归，但我可以使用私有方法。

到目前为止，这是多么有：

public static bool findSequence(char[] findIn, char[] toFind) 
{ 
    return compare(findIn, toFind, num); 
} 

private static int num = 0; 

private static bool compare(char[] findIn, char[] toFind, int num) 
{ 
    for (int i = 0; i < findIn.Length; i++) 
    { 
     if (toFind[i] != findIn[num]) 
     { 
      num++; 
      return false; 
     } 
    } 

    num++; 
    return true; 
} 

Answer 1

你是在错误的方式，因为你必须使用递归，避免循环，你的代码中有循环，也没有递归。我认为你应该尝试一点，因为这对健脑非常有用。无论如何，这应该工作（甚至理解这可能是一个很好的锻炼:-)）：

public static bool FindSequence(char[] findIn, char[] toFind) 
    { 
     return FindSequence(findIn, toFind, 0, 0); 
    } 

    private static bool FindSequence(char[] findIn, char[] toFind, int posInFindIn, int posInToFind) 
    { 
     if (findIn.Length - posInFindIn < toFind.Length - posInToFind) 
      return false; 
     if (findIn[posInFindIn] == toFind[posInToFind]) 
     { 
      if (posInToFind == toFind.Length - 1) 
       return true; 
      else 
       if (FindSequence(findIn, toFind, posInFindIn + 1, posInToFind + 1)) 
        return true; 
     } 
     return FindSequence(findIn, toFind, posInFindIn + 1, 0); 
    } 

Answer 2

下面是代码的用于检查的简化版本findIn是否包含在其的toFind子阵开始（而比沿着其长度的任何地方）：

public static bool FindSequence(char[] findIn, char[] toFind) 
{ 
    return findIn.Length >= toFind.Length && 
      FindSequence(findIn, toFind, 0); 
} 

private static bool FindSequence(char[] findIn, char[] toFind, int pos) 
{ 
    return pos < toFind.Length && 
      findIn[pos] == toFind[pos] && 
      FindSequence(findIn, toFind, pos + 1); 
} 

Answer 3

下面是使用一个类构建体和一个队列以寻找所述子阵列的精确指数一个答案。

namespace Alogrithms 
{ 
    public class ArraySearch 
    { 
    int[] pattern; 
    Queue<int> indices = new Queue<int>(); 
    int[] source; 
    public ArraySearch(int[] pattern, int[] source) 
    { 
     this.source = source; 
     this.pattern = pattern; 
    } 
    public int[] Pattern 
    { 
     get { return pattern; } 
     private set { pattern = value; } 
    } 
    public Queue<int> Indices 
    { 
     get { return indices; } 
     private set { indices = value; } 
    } 
    public int SearchForSubArray(int patternIndexPtr,int sourceIndexPtr, ref int[] source) 
    { 
     int end = source.Length; 
     if(patternIndexPtr >= pattern.Length || sourceIndexPtr >= end) 
     return patternIndexPtr; 

     if(pattern[patternIndexPtr] == source[sourceIndexPtr]) 
     { 
     indices.Enqueue(sourceIndexPtr); 
     return SearchForSubArray(patternIndexPtr + 1,sourceIndexPtr+1, ref source); 
     } 
     else 
     { 
     indices.Clear(); 
     patternIndexPtr = 0; 
     return SearchForSubArray(patternIndexPtr, sourceIndexPtr + 1, ref source); 
     } 
    } 
    } 
} 

类用法：

 int [] randomArray = new int[]{9,8,9,6,5,6,4,7,8,5,4,5,6,3,2,1,3,5,6,5,5,9,6,3,4,5,7,6,8,9,6,7,8,9,9,9,8,2,1,3,5,6,5,5,9,6,3,4,5,7,6,8,9,9,9,9,8}; 
     int[] pattern = new int[] { 6, 7, 8 }; 
     ArraySearch sequence = new ArraySearch(randomArray,pattern); 
     int found = sequence.SearchForSubArray(0, 0, ref randomArray); 
     Console.WriteLine("found : " + found); 
     Console.WriteLine("Pattern is : " + String.Join(",", sequence.Pattern)); 
     foreach(int point in sequence.Indices) 
     { 
     Console.WriteLine(point); 
     } 
     if (sequence.Indices.Count == 0) 
     { 
     Console.WriteLine("Sequence not found."); 
     } 
     Console.ReadLine();