Mercurial > hg > Members > masakoha > testcode
changeset 41:e1c5ecbf8836
add bmsearch.cc
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 02 Mar 2015 23:35:10 +0900 |
parents | c25b75f764a7 |
children | cdb4fd81c31f |
files | regex/Makefile regex/bmsearch.cc regex/main.cc |
diffstat | 3 files changed, 73 insertions(+), 45 deletions(-) [+] |
line wrap: on
line diff
--- a/regex/Makefile Mon Mar 02 22:18:37 2015 +0900 +++ b/regex/Makefile Mon Mar 02 23:35:10 2015 +0900 @@ -1,10 +1,25 @@ TARGET=regex +CC=clang++ OPTION= -Wall -O0 -g -$(TARGET):main.cc - clang $(OPTION) -o $(TARGET) main.cc +SRCS_TMP = $(wildcard *.cc) +SRCS_EXCLUDE = # 除外するファイルを書く +SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP)) +OBJS = $(SRCS:.cc=.o) + +.SUFFIXES: .cc .o + +.cc.o: + $(CC) $(CFLAGS) -c $< -o $@ + +all: $(TARGET) + +$(TARGET):$(OBJS) + $(CC) -o $@ $(OBJS) clean: - rm -f $(TARGET) - rm -r $(TARGET).dSYM + rm -f $(TARGET) $(OBJS) rm -f *~ \#* + +test: + ./$(TARGET) -file main.cc -sw bm
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/regex/bmsearch.cc Mon Mar 02 23:35:10 2015 +0900 @@ -0,0 +1,51 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <math.h> +#include <string.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <fcntl.h> +#include "regex.h" + +//Boyer Moore法に使用するテーブルを作成 +int * +createBMskiptable(BMDataPtr bmdata) +{ + int searchWordLen = bmdata->searchWordLen; + char *searchWord = bmdata->searchWord; + int* skipTable = (int*)malloc(sizeof(int)*256); + + for(int i = 0; i < 256; ++i){ + bmdata->skipTable[i] = searchWordLen; + } + + for(int j = 0; j < searchWordLen - 1; ++j){ + bmdata->skipTable[(u_char)searchWord[j]] = searchWordLen - j - 1; + } + return skipTable; +} + +//Boyer Moore法による文字列検索アルゴリズム +void* BMmethod(BMDataPtr bmdata,ResultPtr result) +{ + int i = bmdata->searchWordLen - 1; + int matchCounter = 0; + + while ( i < bmdata->readTextLen){ + int j = bmdata->searchWordLen - 1; + while (bmdata->readText[i] == bmdata->searchWord[j]){ + if (j == 0){ + matchCounter++; + } + --i; + --j; + } + i = i + fmax(bmdata->skipTable[(u_char)bmdata->readText[i]],bmdata->searchWordLen - j); + } + + result->matchNum = matchCounter; + return result; +} +
--- a/regex/main.cc Mon Mar 02 22:18:37 2015 +0900 +++ b/regex/main.cc Mon Mar 02 23:35:10 2015 +0900 @@ -7,49 +7,11 @@ #include <sys/stat.h> #include <sys/types.h> #include <fcntl.h> -#include "Regex.h" +#include "regex.h" const char *usr_help_str = "Usage: ./regex [-file filename] [-sw SearchWord]\n"; - -//Boyer Moore法に使用するテーブルを作成 -int * -createBMskiptable(BMDataPtr bmdata) -{ - int searchWordLen = bmdata->searchWordLen; - char *searchWord = bmdata->searchWord; - int* skipTable = (int*)malloc(sizeof(int)*256); - - for(int i = 0; i < 256; ++i){ - bmdata->skipTable[i] = searchWordLen; - } - - for(int j = 0; j < searchWordLen - 1; ++j){ - bmdata->skipTable[(u_char)searchWord[j]] = searchWordLen - j - 1; - } - return skipTable; -} - -//Boyer Moore法による文字列検索アルゴリズム -static void* BMmethod(BMDataPtr bmdata,ResultPtr result) -{ - int i = bmdata->searchWordLen - 1; - int matchCounter = 0; - - while ( i < bmdata->readTextLen){ - int j = bmdata->searchWordLen - 1; - while (bmdata->readText[i] == bmdata->searchWord[j]){ - if (j == 0){ - matchCounter++; - } - --i; - --j; - } - i = i + fmax(bmdata->skipTable[(u_char)bmdata->readText[i]],bmdata->searchWordLen - j); - } - - result->matchNum = matchCounter; - return result; -} +extern int *createBMskiptable(BMDataPtr); +extern void *BMmethod(BMDataPtr,ResultPtr); int main(int argc, char* argv[]) {