fv.c

SBMH算法。为字符串匹配算法。c语言开发。

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#include "FV.h"

//this will create an acsm struct that has no pattern in it
struct acsm * acsmNew() {
	//create the root the pattern trie
	pattern_trie p_new_trie = (pattern_trie)malloc(sizeof(pattern_trie_node));
	//create the acsm structure
	struct acsm* p_new_acsm = (struct acsm*)malloc(sizeof(struct acsm));

	p_new_trie->n_pattern_end = 0;
	p_new_acsm->n_pattern_number = 0;
	p_new_acsm->n_min_length = 0;
	p_new_acsm->p_trie_root = p_new_trie;
	for (int i=0; i<CHAR_SET_SIZE; i++) {
		p_new_trie->p_next_char[i] = NULL;
		p_new_acsm->n_BCH[i] = -1;
	}

	return p_new_acsm;
};

//this will add a single pattern to the acsm structure
int acsmAddPattern(struct acsm* p_acsm, char* p_pattern, int n_pattern_length) {
	if (p_acsm==NULL || p_pattern==NULL)
		return 0; //error. acsm or pattern does not exist

	pattern_trie_node* p = p_acsm->p_trie_root;
	pattern_trie_node* p_temp_node = NULL;
	int i,j;

	//add the pattern to the trie structure
	for (i=n_pattern_length-1; i>=0; i--) {
		if (p->p_next_char[*(p_pattern+i)] != NULL) {
			p = p->p_next_char[*(p_pattern+i)];			
		}
		else {
			p_temp_node = (pattern_trie_node*)malloc(sizeof(pattern_trie_node));

			p_temp_node->n_pattern_end = 0;
			for (j=0; j<CHAR_SET_SIZE; j++)
				p_temp_node->p_next_char[j] = NULL;

			p->p_next_char[*(p_pattern+i)] = p_temp_node;
			p = p_temp_node;
		}
	}
	//this is a new pattern or not
	//p is the end of the pattern
	if (p->n_pattern_end != 1) {
		p->n_pattern_end = 1;
		p_acsm->n_pattern_number++;
	}

	//refresh the BCH function
	/*char* p_reverse_pattern = (char*)malloc(n_pattern_length*sizeof(char));
	for (i=0; i<n_pattern_length; i++) {
		p_reverse_pattern[i] = p_pattern[n_pattern_length-i-1];
	}*/
	int n_char_BCH;
	for (i=0; i<CHAR_SET_SIZE; i++) {
		n_char_BCH = -1;
		for (j=n_pattern_length-1; j>=0; j--) {
			if (*(p_pattern+j) == i)
				n_char_BCH = n_pattern_length-1-j;
		}
		//for character which is not in this pattern
		if (n_char_BCH == -1) n_char_BCH = n_pattern_length;

		//refresh the BCH of this trie
		if (p_acsm->n_BCH[i] == -1 || n_char_BCH < p_acsm->n_BCH[i])
			p_acsm->n_BCH[i] = n_char_BCH;
	}

	//refresh the length of the shortest pattern if possible
	if (p_acsm->n_min_length == 0 || n_pattern_length < p_acsm->n_min_length)
		p_acsm->n_min_length = n_pattern_length;

	return 1; //add pattern successfully
}

//there is no operation in this function
int acsmCompile(struct acsm* p_acsm) {return 1;}

//the main search function
int acsmSearch(struct acsm* p_acsm, char* p_text, long l_text_length) {
	if (p_acsm==NULL || p_text==NULL)
		return 0; //error.acsm or text does not exist

	char* p_output_str; //the pointer to the string that has just been found
	long l_str_position; //the position of the found string in the text

	long e = p_acsm->n_min_length-1; //the start position in the text

	char* p_char = NULL; //the pointer to the char in the text to be compare with

	int s = 0; //number of shift steps

	pattern_trie_node* p = p_acsm->p_trie_root; //the pointer to the trie

	int i;

	while (e < l_text_length)
	{
		i = 0;
		p_char = p_text+e-i;
		p = p_acsm->p_trie_root;

		//found different char or reach the beginning of the text
		while (p->p_next_char[*p_char] != NULL && e-i>0)
		{
			p = p->p_next_char[*p_char];
			i++;
			p_char = p_text+e-i;

			if (p->n_pattern_end == 1) {
				p_output_str = (char*)malloc((i+1)*sizeof(char));
				l_str_position = e-i+2;
				memcpy(p_output_str, p_char+1, i);
				p_output_str[i] = '\0';
				printf("%s\t\t%ld\n",p_output_str,l_str_position); //can be changed to other output way
				delete p_output_str;
			}
		}

		if (p->p_next_char[*p_char] == NULL) { //found a different char,use BCH to shift e
			s = p_acsm->n_BCH[*p_char]-i;
			e = e+(s>0?s:1);
		}
		else {
			e++;
		}
	}
}

//delete the data structure acsm
int acsmDestroy(struct acsm* p_acsm) {
	if (p_acsm == NULL)
		return 0; //error. p_acsm does not exist
	
	int r = trieDelete(p_acsm->p_trie_root);
	delete p_acsm;

	return r;
}

//delete a trie
int trieDelete(pattern_trie p_trie) {
	for (int i=0; i<CHAR_SET_SIZE; i++)
		if (p_trie->p_next_char[i] != NULL)
			trieDelete(p_trie->p_next_char[i]);
	
	delete p_trie;
	return 1;
}