字节数组查找算法
public static class Algorithm
{
public static int BmSerach(byte[] source, byte[] template)
{
// Prepare BmBc
int[] bmBc = new int[256];
for (int i = 0; i < bmBc.Length; ++i)
bmBc[i] = template.Length;
for (int i = 0; i < template.Length - 1; ++i)
bmBc[template[i]] = template.Length - 1 - i;
// Prepare Suffix
int[] suff = new int[template.Length];
suff[suff.Length - 1] = template.Length;
for (int i = template.Length - 2; i >= 0; --i)
{
int q = i;
while (q >= 0 && template[q] == template[template.Length - 1 - (i - q)])
--q;
suff[i] = i - q;
}
// Prepare BmGs
int[] bmGs = new int[template.Length];
for (int i = 0; i < bmGs.Length - 1; i++)
bmGs[i] = template.Length;
int j = 0;
for (int i = template.Length - 1; i >= 0; --i)
if (suff[i] == i + 1)
for (; j < template.Length - 1 - i; ++j)
if (bmGs[j] == template.Length)
bmGs[j] = template.Length - 1 - i;
for (int i = 0; i <= template.Length - 2; ++i)
bmGs[template.Length - 1 - suff[i]] = template.Length - 1 - i;
// Search
j = 0;
while (j < source.Length - template.Length)
{
int i = template.Length - 1;
for (; i >= 0 && template[i] == source[j + i]; i--) ;
if (i < 0)
return j;
else
{
int step = Math.Max(bmBc[source[j + i]], bmGs[i]);
j += step;
}
}
return -1;
}
public static int Sunday(byte[] source, byte[] template)
{
int i, pos = 0;
int len_s, len_d;
int[] alphabet = new int[256];
alphabet[0] = 0;
len_s = source.Length;
len_d = template.Length;
for (i = 0; i < 256; i++)
alphabet[i] = len_d;
for (i = 0; i < len_d; i++)
alphabet[template[i]] = len_d - i - 1;
for (pos = 1; pos <= len_s - len_d;)
{
for (i = pos - 1; i - pos + 1 < len_d; i++)
{
if (source[i] != template[i - pos + 1])
break;
}
if ((i - pos + 1) == len_d)
return pos-1;
else
pos += alphabet[source[pos + len_d - 1]] + 1;
}
return -1;
}
}