Mercurial > hg > Applications > Grep

comparison regex/main.cc @ 41:e1c5ecbf8836

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
40:c25b75f764a7 41:e1c5ecbf8836
5 #include <string.h> 5 #include <string.h>
6 #include <sys/mman.h> 6 #include <sys/mman.h>
7 #include <sys/stat.h> 7 #include <sys/stat.h>
8 #include <sys/types.h> 8 #include <sys/types.h>
9 #include <fcntl.h> 9 #include <fcntl.h>
10 #include "Regex.h" 10 #include "regex.h"
11 11
12 const char *usr_help_str = "Usage: ./regex [-file filename] [-sw SearchWord]\n"; 12 const char *usr_help_str = "Usage: ./regex [-file filename] [-sw SearchWord]\n";
13 13 extern int *createBMskiptable(BMDataPtr);
14 //Boyer Moore法に使用するテーブルを作成 14 extern void *BMmethod(BMDataPtr,ResultPtr);
15 int *
16 createBMskiptable(BMDataPtr bmdata)
17 {
18 int searchWordLen = bmdata->searchWordLen;
19 char *searchWord = bmdata->searchWord;
20 int* skipTable = (int*)malloc(sizeof(int)*256);
21
22 for(int i = 0; i < 256; ++i){
23 bmdata->skipTable[i] = searchWordLen;
24 }
25
26 for(int j = 0; j < searchWordLen - 1; ++j){
27 bmdata->skipTable[(u_char)searchWord[j]] = searchWordLen - j - 1;
28 }
29 return skipTable;
30 }
31
32 //Boyer Moore法による文字列検索アルゴリズム
33 static void* BMmethod(BMDataPtr bmdata,ResultPtr result)
34 {
35 int i = bmdata->searchWordLen - 1;
36 int matchCounter = 0;
37
38 while ( i < bmdata->readTextLen){
39 int j = bmdata->searchWordLen - 1;
40 while (bmdata->readText[i] == bmdata->searchWord[j]){
41 if (j == 0){
42 matchCounter++;
43 }
44 --i;
45 --j;
46 }
47 i = i + fmax(bmdata->skipTable[(u_char)bmdata->readText[i]],bmdata->searchWordLen - j);
48 }
49
50 result->matchNum = matchCounter;
51 return result;
52 }
53 15
54 int main(int argc, char* argv[]) { 16 int main(int argc, char* argv[]) {
55 17
56 char *filename = 0; 18 char *filename = 0;
57 char *searchWord = 0; 19 char *searchWord = 0;