forked from pnkapadia6/fast-search
-
Notifications
You must be signed in to change notification settings - Fork 0
/
search_string_serial.c
100 lines (82 loc) · 3 KB
/
search_string_serial.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// Serial implementation of string searching
// a?b gives -> acb, abb, ...
// case insensitive
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int search(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
int cnt = 0;
int i=0,j,k,d=0;
/* A loop to slide pat[] one by one */
for (i = 0; i <= N - M; i++)
{
d=0;
/* Neglecting escape characters */
if(txt[i]=='\n' || txt[i]==' ' || txt[i]=='\t')
continue;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
{
if(pat[j] == '?')
{
continue;
}
if (tolower(txt[i+j]) != tolower(pat[j]))
break;
}
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
// printf("1 at i=%d char->%c\n",i, txt[i]);
if(pat[j-1] == '?' && (txt[i+j-1] == ' ' || txt[i+j-1]=='\n' || txt[i+j-1] == '\0' ));
else
cnt++;
}
}
return cnt;
}
/* Driver program to test above function */
int main()
{
struct timeval total_st, total_stp, kernel_st, kernel_stp, copy_st, copy_stp;
gettimeofday(&total_st,NULL);
char *pat = "ab";
FILE *fp;
char ch;
int cnt=0;
gettimeofday(©_st, NULL);
fp = fopen("big.txt","r"); // read mode
fseek(fp, 0L, SEEK_END);
int sz = ftell(fp);
char txt[sz];
// char * txt=(char *)malloc(sz);
fseek(fp, 0L, SEEK_SET);
if( fp == NULL )
{
perror("Error while opening the file.\n");
exit(EXIT_FAILURE);
}
while( (ch= fgetc(fp) ) != EOF ){
txt[cnt] = ch;
cnt++;
}
txt[cnt]='\0';
fclose(fp);
gettimeofday(©_stp, NULL);
float copy = (copy_stp.tv_sec - copy_st.tv_sec)*1000 + copy_stp.tv_usec/1000.0 - copy_st.tv_usec/1000.0;
printf("copy time-- %f ms\n", copy);
// printf("%s",txt);
gettimeofday(&kernel_st,NULL);
int total = search(pat, txt);
gettimeofday(&kernel_stp,NULL);
printf("Total matches=%d\n",total);
getchar();
gettimeofday(&total_stp,NULL);
float kernel_elapsed = (kernel_stp.tv_sec - kernel_st.tv_sec)*1000 + kernel_stp.tv_usec/1000.0 - kernel_st.tv_usec/1000.0;
float total_elapsed = (total_stp.tv_sec - total_st.tv_sec)*1000 + total_stp.tv_usec/1000.0 - total_st.tv_usec/1000.0;
printf("Kernel time-%fms\n", kernel_elapsed);
printf("Total time-%fms\n", total_elapsed);
return 0;
}