Can you implement the Boyer–Moore-Horspool algorithm for a circular buffer in C?
- User
Can you implement the Boyer–Moore-Horspool algorithm for a circular buffer in C?
- Assistant
Sure! The Boyer-Moore-Horspool (BMH) algorithm is an efficient string-searching algorithm that skips sections of the text to improve performance. When dealing with a circular buffer, we need to adapt the algorithm to account for the buffer wrapping around.
Below is a C implementation of the Boyer-Moore-Horspool algorithm tailored for searching within a circular buffer.
#include <stdio.h> #include <string.h> #include <stdlib.h> #define BUFFER_SIZE 1024 // Example buffer size // Function to build the bad character shift table void build_shift_table(const char *pattern, int pat_len, int shift_table[256]) { for (int i = 0; i < 256; i++) { shift_table[i] = pat_len; // Default shift } for (int i = 0; i < pat_len - 1; i++) { shift_table[(unsigned char)pattern[i]] = pat_len - i - 1; } } // Function to search for a pattern in a circular buffer // Returns the starting index of the pattern in the buffer if found, -1 otherwise int bmh_search_circular(const char *buffer, int buf_start, int buf_len, const char *pattern, int pat_len) { int shift_table[256]; build_shift_table(pattern, pat_len, shift_table); int buf_end = buf_start + buf_len; // Virtual end index (may exceed BUFFER_SIZE) int i = 0; // Current position in the search window while (i <= buf_len - pat_len) { int j = pat_len - 1; // Compare the pattern with the buffer from end to start while (j >= 0 && buffer[(buf_start + i + j) % BUFFER_SIZE] == pattern[j]) { j--; } if (j < 0) { // Match found return (buf_start + i) % BUFFER_SIZE; } else { // Calculate shift based on the next character in the buffer unsigned char next_char = buffer[(buf_start + i + pat_len - 1) % BUFFER_SIZE]; i += shift_table[next_char]; } } // Pattern not found return -1; } int main() { // Example usage // Initialize circular buffer with some data char buffer[BUFFER_SIZE]; memset(buffer, 0, BUFFER_SIZE); // Fill the buffer with a repeating pattern "Hello World!" const char *data = "Hello World!"; int data_len = strlen(data); for (int i = 0; i < BUFFER_SIZE; i++) { buffer[i] = data[i % data_len]; } // Define the pattern to search for const char *pattern = "World"; int pat_len = strlen(pattern); // Define the start position and length of the data in the buffer int buf_start = 500; // Example start position (could be any valid index) int buf_len = 800; // Length of data to search (could wrap around the buffer) // Perform the search int position = bmh_search_circular(buffer, buf_start, buf_len, pattern, pat_len); if (position != -1) { printf("Pattern found at position %d\n", position); } else { printf("Pattern not found\n"); } return 0; }Explanation:
-
Circular Buffer Handling:
- Since the buffer is circular, index calculations use modulo
% BUFFER_SIZEto wrap around. - The search window is defined by
buf_start(starting index) andbuf_len(length of data to search).
- Since the buffer is circular, index calculations use modulo
-
Shift Table Construction:
- The
build_shift_tablefunction creates a shift table based on the pattern. - For each character in the pattern (except the last one), it computes how far the search window can be shifted if a mismatch occurs.
- The
-
Search Function (
bmh_search_circular):- The function searches for the
patternwithin the specified portion of thebuffer. - It uses the BMH algorithm logic adjusted for circular buffer indexing.
- The search continues until there isn't enough remaining data to match the pattern (
i <= buf_len - pat_len). - If a mismatch occurs, the shift distance is determined by the character in the buffer where the mismatch happened.
- The function searches for the
Key Points:
-
Modulo Operations:
- All buffer accesses use modulo to ensure indices wrap around appropriately.
-
Performance Considerations:
- Modulo operations can be computationally expensive inside tight loops.
- Optimizations could include unrolling loops or avoiding modulo when possible.
-
Edge Cases and Testing:
- The code assumes that
buf_lenis at least as large aspat_len. - Test with various
buf_start,buf_len, and patterns to ensure correctness. - Be cautious of patterns that span the end and start of the buffer.
- The code assumes that
Example Output:
If you run the provided
mainfunction, you might see:Pattern found at position 507This indicates that the pattern "World" was found starting at buffer index 507.
Usage Notes:
-
Adjusting Buffer Parameters:
- Modify
BUFFER_SIZE,buf_start, andbuf_lento match your application's buffer size and data.
- Modify
-
Thread Safety:
- If used in a multithreaded environment, ensure that the buffer access is properly synchronized.
-
Function Integration:
- Integrate the
bmh_search_circularfunction into your codebase, ensuring that buffer parameters are correctly managed.
- Integrate the
Let me know if you have any questions or need further clarification!
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.