我正在尝试在 C 中实现 Boyer-Moore 算法以在 .pcap 文件中搜索特定单词。我从http://ideone.com/FhJok5引用了代码。我正在使用此代码。
只是我将数据包作为字符串传递,并将我正在搜索的关键字传递给其中的函数 search()。当我运行我的代码时,它每次都会给出不同的值。有时它也给出了正确的值。但大多数时候它没有识别一些值。
我从 Naive Algo Implementation 获得了结果。结果总是完美的。
我在 VMware 10.0.1 上使用 Ubuntu 12.0.4。语言:C
我的问题是每次都必须给出相同的结果,对吗?不管是对是错。每次我在相同的输入上运行文件时,此输出都会不断变化;并且在几次运行期间,它也给出了正确的答案。大多数情况下,该值在 3 或 4 个值之间变化。
到目前为止我所做的调试:
- 每次都传递字符串而不是数据包,它的工作完美且每次都具有相同和正确的值。
- 检查 pcap 部分,我可以看到所有数据包都被传递给函数(我通过打印数据包帧号来检查)。
- 我发送给 Naive Algo 代码的相同数据包,它提供了完美的代码。
请给我一些想法,可能是什么问题。我怀疑内存管理有问题。但如何找到哪一个?
提前致谢。
# include <limits.h>
# include <string.h>
# include <stdio.h>
# define NO_OF_CHARS 256
// A utility function to get maximum of two integers
int max (int a, int b) { return (a > b)? a: b; }
// The preprocessing function for Boyer Moore's bad character heuristic
void badCharHeuristic( char *str, int size, int badchar[NO_OF_CHARS])
{
int i;
// Initialize all occurrences as -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence of a character
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* A pattern searching function that uses Bad Character Heuristic of
Boyer Moore Algorithm */
void search( char *txt, char *pat)
{
int m = strlen(pat);
int n = strlen(txt);
int badchar[NO_OF_CHARS];
/* Fill the bad character array by calling the preprocessing
function badCharHeuristic() for given pattern */
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with respect to text
while(s <= (n - m))
{
int j = m-1;
/* Keep reducing index j of pattern while characters of
pattern and text are matching at this shift s */
while(j >= 0 && pat[j] == txt[s+j])
j--;
/* If the pattern is present at current shift, then index j
will become -1 after the above loop */
if (j < 0)
{
printf("\n pattern occurs at shift = %d", s);
/* Shift the pattern so that the next character in text
aligns with the last occurrence of it in pattern.
The condition s+m < n is necessary for the case when
pattern occurs at the end of text */
s += (s+m < n)? m-badchar[txt[s+m]] : 1;
}
else
/* Shift the pattern so that the bad character in text
aligns with the last occurrence of it in pattern. The
max function is used to make sure that we get a positive
shift. We may get a negative shift if the last occurrence
of bad character in pattern is on the right side of the
current character. */
s += max(1, j - badchar[txt[s+j]]);
}
}
/* Driver program to test above function */
int main()
{
char txt[] = "ABAAAABAACD";
char pat[] = "AA";
search(txt, pat);
return 0;