Array existance check

[bluesapphire]

Hi!
I have two arrays .
First Array = 2,-3,4,7,11,5,-1,-9,13,55
Second Array = 5,-1,-9,13

How can i verify through algorithm that second array exists [in same order] in first array. In other words that I want to verify that second array is sub array of first array.


Thanks in advance

[Zachm]

Hi,

I will try in C++:


bool IsSubArray(int *array, int arrSize, int *subArray, int subSize)
{
int subIndex = 0;
int arrIndex = 0;
int maxIndex;

if (subSize > arrSize)
{
return false;
}

maxIndex = arrSize - subSize + 1;

while ( (arrIndex < maxIndex + subIndex) && (subIndex < subSize) )
{
if (array[arrIndex] == subArray[subIndex])
{
subIndex++;
}
else
{
subIndex = 0;
}

arrIndex++;
}

return (subIndex == subSize);
}


I think it's quite simple to understand. If you have any questions, I'll try to answer.

[gmrowe1075]

If you are going to be doing a lot of these kinds of searches like this and you want to optimize time and space, you could implement a version of the much more complex Boyer Moore algorithm (http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm)

[James2007]

template <typename Type> bool FindSubArray(const Type * pArray, unsigned long dwLength, const Type * pSubArray, unsigned long dwSubLen, unsigned long * pdwFoundIndex) throw()
{
if (pArray != 0 && pSubArray != 0 && dwSubLen != 0 && dwSubLen <= dwLength && pdwFoundIndex != 0)
{
const unsigned long dwLastIndex = dwLength - dwSubLen;

unsigned long * pdwPossibleIndices = new unsigned long[dwLastIndex + 1];
unsigned long dwPossibleCount(0);

for (unsigned long x = 0; x <= dwLastIndex; ++x)
{
if (pArray[x] == pSubArray[x])
{
pdwPossibleIndices[dwPossibleCount] = x;
++dwPossibleCount;
}
}

bool bFound(false);

if (dwPossibleCount != 0)
{
unsigned long dwIndex(0);

for (unsigned long i = 0; i < dwPossibleCount; ++i)
{
dwIndex = pdwPossibleIndices[i];

bFound = true;

for (unsigned long v = 1; v < dwSubLen; ++v) // start with 1, because first index we know matches
{
if (pArray[dwIndex + v] != pSubArray[v])
{
bFound = false;
break;
}
}

if (bFound == true)
{
*pdwFoundIndex = dwIndex;
break;
}
}
}

delete [] pdwPossibleIndices; // DO NOT FORGET TO FREE

return bFound;
}

return false;
}


Actually, it's not hard at all. >_<

I looked at the code listed in the link, and I didn't even want to sort throught it. It was *ugly*. The code above is clear, and SIMPLE. Not to mention reusable, because it's a template.

Basically, it checks the first element of the sub array versus all the elements from the beginning of the specified array to the last valid index where a sub array could be found. ("Length of Array" - "Length of Sub Array") If they match, stores the index in an array itself.

If there are any possible matches, loops again (with the number of possible matches used) and retrieves the index that was 'possible'. Another loop (starting from one index past since the first was already matched) compares the remaining elements in the sub array to the elements beyond the 'possible index'.

If none of the elements 'do not match' then a match was made. And the index is set in the 'pointer parameter' and the loop is exited.

It does need to allocate a buffer to store 'indices' though. If you have 500000 elements, and the sub array is 1 element it will require 2,000,000 bytes of dynamic memory ( 500000 * sizeof(unsigned long) ) to store those 'indices'. That is 1.9073486328125 megabytes required. The memory requirements.

This means it 'should' be modified to handle 'single element' sub arrays. (Searching for a single element sub array would require no 'checking for possible', so no extra memory would be required.)

I'll let you figure that out (I could do it with ease, but I do not want to do all your work for you.) :ehh:

But I will give the alternative for no memory allocations in the find function.



template <typename Type> bool FindSubArrayNoMem(const Type * pArray, unsigned long dwLength, const Type * pSubArray, unsigned long dwSubLen, unsigned long * pdwFoundIndex) throw()
{
if (pArray != 0 && pSubArray != 0 && dwSubLen != 0 && dwSubLen <= dwLength && pdwFoundIndex != 0)
{
const unsigned long dwLastIndex = dwLength - dwSubLen;

bool bFound(false);

for (unsigned long x = 0; x <= dwLastIndex; ++x)
{
bFound = true;

for (unsigned long i = 0; i < dwSubLen; ++i)
{
if (pArray[x + i] != pSubArray[i])
{
bFound = false;
break;
}
}

if (bFound == true)
{
*pdwFoundIndex = x;
break;
}
}

return bFound;
}

return false;
}