Skip to content

Commit fc291f8

Browse files
author
Miao Mico
committed
初步实现 sunday algorithm;
1 parent a5bf401 commit fc291f8

8 files changed

Lines changed: 270 additions & 3 deletions

File tree

‎Algorithm/algorithm.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,8 @@
1616
*********************************************************************************************************
1717
*/
1818

19+
#include "string_matching.h"
20+
1921
#include "compare.h"
2022

2123
#include "sort.h"

‎Algorithm/string_matching.c‎

Lines changed: 151 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,151 @@
1+
/*
2+
*********************************************************************************************************
3+
* INCLUDE FILES
4+
*********************************************************************************************************
5+
*/
6+
7+
#include "string_matching.h"
8+
9+
/*
10+
*********************************************************************************************************
11+
* LOCAL DEFINES
12+
*********************************************************************************************************
13+
*/
14+
15+
/*
16+
*********************************************************************************************************
17+
* LOCAL CONSTANTS
18+
*********************************************************************************************************
19+
*/
20+
21+
/*
22+
*********************************************************************************************************
23+
* LOCAL DATA TYPES
24+
*********************************************************************************************************
25+
*/
26+
27+
/*
28+
*********************************************************************************************************
29+
* LOCAL TABLES
30+
*********************************************************************************************************
31+
*/
32+
33+
/*
34+
*********************************************************************************************************
35+
* LOCAL GLOBAL VARIABLES
36+
*********************************************************************************************************
37+
*/
38+
39+
/*
40+
*********************************************************************************************************
41+
* LOCAL FUNCTION PROTOTYPES
42+
*********************************************************************************************************
43+
*/
44+
45+
/*
46+
*********************************************************************************************************
47+
* FUNCTIONS
48+
*********************************************************************************************************
49+
*/
50+
51+
/**
52+
* @brief This function will search the substring upon the string by the sunday algorithm.
53+
*
54+
* @param str the pointer to the string.
55+
* @param substr the pointer to the substring.
56+
* @param len the length of the substring.
57+
*
58+
* @return the max matching rate.
59+
*/
60+
61+
float substring_search_control_sunday_algorithm(const char *str, size_t len,
62+
const char *substr, size_t sublen)
63+
{
64+
assert(str);
65+
assert(len);
66+
assert(substr);
67+
assert(sublen);
68+
69+
static size_t
70+
loc, step, subloc;
71+
72+
static char
73+
symbol_substr;
74+
75+
static float
76+
max_matching_rate;
77+
78+
struct sunday_algorith_substring_infomation_s {
79+
bool exist;
80+
81+
size_t location;
82+
}symbol[128] = { 0 }; /* ASSIC have 128 symbol */
83+
84+
loc = 0; /* Set zero */
85+
step = 0;
86+
subloc = 0;
87+
max_matching_rate = 0.0;
88+
89+
do { /* Get the information of the substring,
90+
whether the symbol exist and where it is */
91+
symbol_substr = *(substr + subloc);
92+
93+
if (false == symbol[symbol_substr].exist) {
94+
symbol[symbol_substr].exist = true;
95+
}
96+
97+
symbol[symbol_substr].location = sublen - subloc - 1;
98+
} while (subloc++ < sublen);
99+
100+
do {
101+
subloc = 0;
102+
do {
103+
symbol_substr = *(str + loc + subloc);
104+
105+
if (*(substr + subloc) != symbol_substr) {
106+
#if (STRING_MATCHING_CFG_DEBUG_EN)
107+
108+
printf("substring_search.sunday_algorithm.not match:str \'%c\' - substr \'%c\' the point is \'%c\' \r\n",
109+
*(substr + subloc), symbol_substr, *(str + loc + sublen));
110+
111+
#endif // (STRING_MATCHING_CFG_DEBUG_EN)
112+
113+
symbol_substr = *(str + loc + sublen);
114+
115+
if (true == symbol[symbol_substr].exist) {
116+
#if (STRING_MATCHING_CFG_DEBUG_EN)
117+
118+
printf("substring_search.sunday_algorithm.not match.point is exist \r\n");
119+
120+
#endif // (STRING_MATCHING_CFG_DEBUG_EN)
121+
122+
step = symbol[symbol_substr].location + 1;
123+
} else {
124+
#if (STRING_MATCHING_CFG_DEBUG_EN)
125+
126+
printf("substring_search.sunday_algorithm.not match.point is not exist \r\n");
127+
128+
#endif // (STRING_MATCHING_CFG_DEBUG_EN)
129+
130+
step = sublen + 1;
131+
}
132+
133+
#if (STRING_MATCHING_CFG_DEBUG_EN)
134+
135+
printf("substring_search.sunday_algorithm.step:%d \r\n", step);
136+
137+
#endif // (STRING_MATCHING_CFG_DEBUG_EN)
138+
139+
if (subloc && max_matching_rate < subloc / (float)sublen) {
140+
max_matching_rate = subloc / (float)sublen;
141+
}
142+
143+
break;
144+
} else if (sublen - 1 == subloc) {
145+
return 1.0;
146+
}
147+
} while (subloc++ < sublen);
148+
} while ((loc += step) < len);
149+
150+
return max_matching_rate;
151+
}

‎Algorithm/string_matching.h‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/*
2+
*********************************************************************************************************
3+
* MODULE
4+
*
5+
* Note(s) : (1) This definition header file is protected from multiple pre-processor inclusion
6+
* through use of the definition module present pre-processor macro definition.
7+
*********************************************************************************************************
8+
*/
9+
10+
#ifndef __STRING_MATCHING_H
11+
#define __STRING_MATCHING_H
12+
13+
/*
14+
*********************************************************************************************************
15+
* INCLUDE FILES
16+
*********************************************************************************************************
17+
*/
18+
19+
#include "algorithm_def.h"
20+
21+
/*
22+
*********************************************************************************************************
23+
* DEFINES
24+
*********************************************************************************************************
25+
*/
26+
27+
/* Configure if enable string matching debug. */
28+
#define STRING_MATCHING_CFG_DEBUG_EN 1u
29+
30+
/*
31+
*********************************************************************************************************
32+
* DATA TYPES
33+
*********************************************************************************************************
34+
*/
35+
36+
/*
37+
*********************************************************************************************************
38+
* FUNCTION PROTOTYPES
39+
*********************************************************************************************************
40+
*/
41+
42+
/**
43+
* @brief This function will search the substring upon the string by the sunday algorithm.
44+
*
45+
* @param str the pointer to the string.
46+
* @param substr the pointer to the substring.
47+
* @param len the length of the substring.
48+
*
49+
* @return the max matching rate.
50+
*/
51+
52+
float substring_search_control_sunday_algorithm(const char *str, size_t len,
53+
const char *substr, size_t sublen);
54+
55+
/*
56+
*********************************************************************************************************
57+
* EXTERN GLOBAL VARIABLES
58+
*********************************************************************************************************
59+
*/
60+
61+
/*
62+
*********************************************************************************************************
63+
* MODULE END
64+
*********************************************************************************************************
65+
*/
66+
67+
#endif // !__STRING_MATCHING_H

‎Main/main.c‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,12 @@ void main(void)
88

99
#endif
1010

11+
#if (MAIN_ALGORITHM_EN)
12+
13+
main_algorithm();
14+
15+
#endif
16+
1117
#if (MAIN_ALLOCATOR_EN)
1218

1319
main_allocator();

‎Main/main_algorithm.c‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#include "algorithm.h"
2+
3+
#include "main_cfg.h"
4+
5+
void main_algorithm(void)
6+
{
7+
char
8+
string[] = "substring searching algorithm",
9+
substring[] = "search";
10+
11+
printf("\r\n ------------------------+ algorithm demo start +------------------------\r\n");
12+
13+
printf("algorithm.substring_search:%f \r\n", substring_search_control_sunday_algorithm(string,
14+
strlen(string),
15+
substring,
16+
strlen(substring)));
17+
18+
printf("\r\n ------------------------+ algorithm demo end +------------------------ \r\n");
19+
20+
return;
21+
}

‎Main/main_cfg.h‎

Lines changed: 11 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,15 +9,17 @@
99

1010
#define MAIN_DEBUG_COMPONENT_EN 0u
1111

12+
#define MAIN_ALGORITHM_EN 1u
13+
1214
#define MAIN_ALLOCATOR_EN 0u
1315

1416
#define MAIN_GENERIC_TYPE_EN 0u
1517

16-
#define MAIN_B_TREE_EN 1u
18+
#define MAIN_B_TREE_EN 0u
1719

18-
#define MAIN_BINARY_SEARCH_TREE_EN 1u
20+
#define MAIN_BINARY_SEARCH_TREE_EN 0u
1921

20-
#define MAIN_RED_BLACK_TREE_EN 1u
22+
#define MAIN_RED_BLACK_TREE_EN 0u
2123

2224
#define MAIN_ARRAY_EN 0u
2325

@@ -41,6 +43,12 @@ void main_debug_component(void);
4143

4244
#endif
4345

46+
#if (MAIN_ALGORITHM_EN)
47+
48+
void main_algorithm(void);
49+
50+
#endif
51+
4452
#if (MAIN_ALLOCATOR_EN)
4553

4654
void main_allocator(void);

‎stack.vcxproj‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121
<ItemGroup>
2222
<ClCompile Include="Algorithm\compare.c" />
2323
<ClCompile Include="Algorithm\sort.c" />
24+
<ClCompile Include="Algorithm\string_matching.c" />
2425
<ClCompile Include="Allocator\allocator_common.c" />
2526
<ClCompile Include="Container\Container adaptors\container_adaptor_def.c" />
2627
<ClCompile Include="Container\Container adaptors\priority_queue.c" />
@@ -41,6 +42,7 @@
4142
<ClCompile Include="Container\Tree\tree_family.c" />
4243
<ClCompile Include="Debug Component\debug_stack_back_trace.c" />
4344
<ClCompile Include="Main\main.c" />
45+
<ClCompile Include="Main\main_algorithm.c" />
4446
<ClCompile Include="Main\main_allocator.c" />
4547
<ClCompile Include="Main\main_array.c" />
4648
<ClCompile Include="Main\main_binary_search_tree.c" />
@@ -61,6 +63,7 @@
6163
<ClInclude Include="Algorithm\algorithm_def.h" />
6264
<ClInclude Include="Algorithm\compare.h" />
6365
<ClInclude Include="Algorithm\sort.h" />
66+
<ClInclude Include="Algorithm\string_matching.h" />
6467
<ClInclude Include="Allocator\allocator.h" />
6568
<ClInclude Include="Allocator\allocator_cfg.h" />
6669
<ClInclude Include="Allocator\allocator_common.h" />

‎stack.vcxproj.filters‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -177,6 +177,12 @@
177177
<ClCompile Include="Container\Squence container\vector.c">
178178
<Filter>源文件\container\sequence containers</Filter>
179179
</ClCompile>
180+
<ClCompile Include="Algorithm\string_matching.c">
181+
<Filter>源文件\algorithm</Filter>
182+
</ClCompile>
183+
<ClCompile Include="Main\main_algorithm.c">
184+
<Filter>源文件\main</Filter>
185+
</ClCompile>
180186
</ItemGroup>
181187
<ItemGroup>
182188
<ClInclude Include="Container\container.h">
@@ -278,5 +284,8 @@
278284
<ClInclude Include="Container\Tree\tree_family.h">
279285
<Filter>头文件\container\tree</Filter>
280286
</ClInclude>
287+
<ClInclude Include="Algorithm\string_matching.h">
288+
<Filter>头文件\algorithm</Filter>
289+
</ClInclude>
281290
</ItemGroup>
282291
</Project>

0 commit comments

Comments
 (0)