AnonGod
IS-IT--Management
- Jun 5, 2000
- 223
I'm looking for something that I can plug 2 byte arrays into and get an index returned of the first occurrence of the first array in the second array.
Found this link that does what I want it to do, but I do not understand the use of the failure array.
I see failure[] is an array that matches the size of the pattern array and contains 0,1,2,3... if the first element in the pattern array matches the 2nd, the 2nd matches the 3rd, etc... and will output all 0's if the 1st does not match the 2nd.
It then uses this in the indexOf method to determine how far to "backup" in the pattern array when part of the pattern array is not found in the data array.
So, I guess what I'm not understanding conceptually is how the failure[] array works. I would be grateful for an explanation and sample data that illustrates how it works.
Thank you!
Here is my sample data:
[Signature modified by admin request]
-TAG
'Drawing on my fine command of language, I said nothing.'
Found this link that does what I want it to do, but I do not understand the use of the failure array.
I see failure[] is an array that matches the size of the pattern array and contains 0,1,2,3... if the first element in the pattern array matches the 2nd, the 2nd matches the 3rd, etc... and will output all 0's if the 1st does not match the 2nd.
It then uses this in the indexOf method to determine how far to "backup" in the pattern array when part of the pattern array is not found in the data array.
So, I guess what I'm not understanding conceptually is how the failure[] array works. I would be grateful for an explanation and sample data that illustrates how it works.
Thank you!
Here is my sample data:
Code:
public static void main(String[] args)
{
byte[] data = {1,2,3,4};
byte[] pattern = {3,4};
int result = indexOf(data,pattern);
System.out.println("Result: " + result);
}
public static int indexOf(byte[] data, byte[] pattern)
{
int[] failure = computeFailure(pattern);
int j = 0;
if (data.length == 0) return -1;
for (int i = 0; i < data.length; i++) {
while (j > 0 && pattern[j] != data[i])
{
j = failure[j - 1];
}
if (pattern[j] == data[i]) { j++; }
if (j == pattern.length)
{
return i - pattern.length + 1;
}
}
return -1;
}
/**
* Computes the failure function using a boot-strapping process,
* where the pattern is matched against itself.
*/
private static int[] computeFailure(byte[] pattern)
{
int[] failure = new int[pattern.length];
int j = 0;
for (int i = 1; i < pattern.length; i++)
{
System.out.println("i: " + i);
while (j > 0 && pattern[j] != pattern[i])
{
System.out.println("j: " + j);
j = failure[j - 1];
}
if (pattern[j] == pattern[i])
{
j++;
}
failure[i] = j;
}
return failure;
}
[Signature modified by admin request]
-TAG
'Drawing on my fine command of language, I said nothing.'