問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2531思路:
更像是枚舉的搜索，外加一個(gè)簡(jiǎn)單的對(duì)稱性減枝，不過(guò)耗時(shí)比較久
代碼:
1 #define MAX_NUM 21
2 int matrix[MAX_NUM][MAX_NUM];
3 int mark[MAX_NUM], mark_num;
4 int num, max;
5
6 int
7 calculate()
8 {
9 int i, j;
10 int sum = 0;
11 for(i=0; i<num; i++)
12 if(mark[i]) {
13 for(j=0; j<num; j++)
14 if(!mark[j])
15 sum += matrix[i][j];
16 }
17 return sum;
18 }
19
20 void
21 dfs(int depth)
22 {
23 int rt;
24 if(depth == num) {
25 rt = calculate();
26 max = rt>max ? rt : max;
27 return;
28 }
29 ++mark_num;
30 mark[depth] = 1; /* mark[depth]=1, put 'depth' into the category I */
31 if(mark_num <= (num>>1)) /* pruning */
32 dfs(depth+1);
33 --mark_num;
34 mark[depth] = 0;
35 dfs(depth+1); /* put 'depth' into the category II */
36 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1606http://acm.pku.edu.cn/JudgeOnline/problem?id=3414思路:
典型的BFS
好玩的就是如何來(lái)處理輸出，每個(gè)狀態(tài)包含一個(gè)指向前一個(gè)狀態(tài)的指針
代碼:
1 #define QUEUE_LEN 10000
2 #define MAX_VOL 101
3 const char ops[][12] = {
4 "FILL(1)",
5 "FILL(2)",
6 "DROP(1)",
7 "DROP(2)",
8 "POUR(1,2)",
9 "POUR(2,1)" };
10 int vola, volb, target;
11 int head, tail;
12 int visited[MAX_VOL][MAX_VOL];
13 struct EACH {
14 int a, b;
15 int opnum;
16 int opidx;
17 struct EACH *pre;
18 } queue[QUEUE_LEN];
19
20 #define ADD(na, nb, num, idx) ++tail; \
21 queue[tail].a = na; \
22 queue[tail].b = nb; \
23 queue[tail].opnum = num+1; \
24 queue[tail].opidx = idx; \
25 queue[tail].pre = queue+head; \
26 visited[na][nb] = 1;
27
28 void
29 output(struct EACH *item)
30 {
31 if(item == NULL)
32 return;
33 output(item->pre);
34 if(item->opidx >= 0)
35 printf("%s\n", ops[item->opidx]);
36 }
37
38 void
39 bfs()
40 {
41 int cur_a, cur_b, ta, tb, cur_opnum;
42 queue[tail].a = 0;
43 queue[tail].b = 0;
44 queue[tail].opnum = 0;
45 queue[tail].opidx = -1;
46 queue[tail].pre = NULL;
47 visited[0][0] = 1;
48 while(head < tail) {
49 ++head;
50 cur_a = queue[head].a;
51 cur_b = queue[head].b;
52 cur_opnum = queue[head].opnum;
53 if(cur_a==target || cur_b==target) {
54 printf("%d\n", cur_opnum);
55 output(queue+head);
56 return;
57 }
58 if(!visited[vola][cur_b]) { /* FILL(1) */
59 ADD(vola, cur_b, cur_opnum, 0);
60 }
61 if(!visited[cur_a][volb]) { /* FILL(2) */
62 ADD(cur_a, volb, cur_opnum, 1);
63 }
64 if(!visited[0][cur_b]) { /* DROP(1) */
65 ADD(0, cur_b, cur_opnum, 2);
66 }
67 if(!visited[cur_a][0]) { /* DROP(2) */
68 ADD(cur_a, 0, cur_opnum, 3);
69 }
70 /* POUR(1,2) */
71 if(cur_a+cur_b > volb) {
72 ta = cur_a+cur_b-volb;
73 tb = volb;
74 if(!visited[ta][tb]) {
75 ADD(ta, tb, cur_opnum, 4);
76 }
77 } else {
78 ta = 0;
79 tb = cur_a + cur_b;
80 if(!visited[ta][tb]) {
81 ADD(ta, tb, cur_opnum, 4);
82 }
83 }
84 /* POUR(2,1) */
85 if(cur_a+cur_b > vola) {
86 ta = vola;
87 tb = cur_a+cur_b-vola;
88 if(!visited[ta][tb]) {
89 ADD(ta, tb, cur_opnum, 5);
90 }
91 } else {
92 ta = cur_a + cur_b;
93 tb = 0;
94 if(!visited[ta][tb]) {
95 ADD(ta, tb, cur_opnum, 5);
96 }
97 }
98 }
99 printf("impossible\n");
100 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3083思路:
對(duì)于求最短路徑，BFS即可解決，沒有什么難度
該題的難點(diǎn)在于如何求沿左、沿右走的問(wèn)題
剛開始，完全不知道這是什么意思，無(wú)奈只能在網(wǎng)上看代碼，總結(jié)如下:
沿左策略的一般次序: left, up, right, down
沿右策略的一般次序: right, up, left, down
求解的關(guān)鍵是如何根據(jù)前一個(gè)方向以及一般次序來(lái)決定目前訪問(wèn)上下左右四個(gè)方向的順序，例如:
對(duì)于沿左前進(jìn)策略，如果前一個(gè)方向是right，那么訪問(wèn)次序是up, right, down, left(與前一個(gè)方向相反的方向總是放在最后)
代碼:
1 #define MAX_LEN 42
2 #define QUEUE_LEN 1600
3 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
4 char maze[MAX_LEN][MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col;
7 int start_x, start_y;
8 /* left, up, right, down */
9 const int dx[] = {0, -1, 0, 1};
10 const int dy[] = {-1, 0, 1, 0};
11 /* right, up, left, down */
12 const int dx_right[] = {0, -1, 0, 1};
13 const int dy_right[] = {1, 0, -1, 0};
14 int lcount, rcount;
15 int head, tail;
16 struct EACH {
17 int x, y;
18 int mv;
19 } queue[QUEUE_LEN];
20
21
22 void
23 init()
24 {
25 int i;
26 char *p;
27 memset(visited, 0, sizeof(visited));
28 head = -1;
29 tail = 0;
30 lcount = rcount = 0;
31 scanf("%d %d", &col, &row);
32 for(i=0; i<row; i++) {
33 scanf("%s", maze[i]);
34 if((p=strchr(maze[i], 'S')) != NULL) {
35 start_x = i;
36 start_y = p-maze[i];
37 }
38 }
39 }
40
41 /*
42 * dir: previous direction
43 * switch(dir):
44 * case(right): up right down left (order)
45 * case(up): left up right down
46 * case(left): down left up right
47 * case(down): right down left up
48 */
49 void
50 dfs_left(int x, int y, int dir)
51 {
52 int i, tx, ty;
53 ++lcount;
54 if(maze[x][y] == 'E') {
55 return;
56 }
57 dir = (dir+3)%4;
58 for(i=0; i<4; i++) {
59 tx = x + dx[(dir+i)%4];
60 ty = y + dy[(dir+i)%4];
61 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
62 dfs_left(tx, ty, (dir+i)%4);
63 break;
64 }
65 }
66 }
67
68 void
69 dfs_right(int x, int y, int dir)
70 {
71 int i, tx, ty;
72 ++rcount;
73 if(maze[x][y] == 'E')
74 return;
75 dir = (dir+3)%4;
76 for(i=0; i<4; i++) {
77 tx = x + dx_right[(dir+i)%4];
78 ty = y + dy_right[(dir+i)%4];
79 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
80 dfs_right(tx, ty, (dir+i)%4);
81 break;
82 }
83 }
84 }
85
86 int
87 bfs()
88 {
89 int i, cx, cy, tx, ty, cmv;
90 memset(visited, 0, sizeof(visited));
91 queue[tail].x = start_x;
92 queue[tail].y = start_y;
93 queue[tail].mv = 1;
94 visited[start_x][start_y] = 1;
95 while(head < tail) {
96 ++head;
97 cx = queue[head].x;
98 cy = queue[head].y;
99 cmv = queue[head].mv;
100 if(maze[cx][cy] == 'E')
101 return cmv;
102 for(i=0; i<4; i++) {
103 tx = cx + dx[i];
104 ty = cy + dy[i];
105 if(is_valid(tx, ty) && !visited[tx][ty] && maze[tx][ty]!='#') {
106 ++tail;
107 queue[tail].x = tx;
108 queue[tail].y = ty;
109 queue[tail].mv = cmv+1;
110 visited[tx][ty] = 1;
111 }
112 }
113 }
114 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3009思路:
這題要求進(jìn)行一個(gè)簡(jiǎn)單的游戲，判斷最優(yōu)步數(shù)。通常來(lái)說(shuō)，這種判斷最短步驟的問(wèn)題可以使用廣度優(yōu)先搜索解決(bfs),由于題目中地圖會(huì)由于游戲的進(jìn)行發(fā)生變化，使用bfs會(huì)比較麻煩（需要記錄地圖狀態(tài)），注意到題目中有一個(gè)條件：只能在10步以內(nèi)完成游戲，于是我們可以考慮使用深度優(yōu)先搜索（dfs）+限制步數(shù)來(lái)完成。簡(jiǎn)單的說(shuō)：就是我們遍歷整個(gè)搜索樹尋找可能解中的最優(yōu)步數(shù)，但當(dāng)搜索樹深度大于10時(shí)則不必繼續(xù)搜索下去。
代碼:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 #define INF 100000
3 #define THROW_MAX 10
4 #define MAX_LEN 21
5 int row, col, start_x, start_y;
6 int board[MAX_LEN][MAX_LEN];
7 int min;
8 const int dx[] = {0, 0, -1, 1};
9 const int dy[] = {-1, 1, 0, 0};
10
11 void
12 dfs(int depth, int x, int y)
13 {
14 int i, tx, ty;
15 if(depth>=THROW_MAX || depth>=min) /* pruning */
16 return;
17 for(i=0; i<4; i++) {
18 tx = x;
19 ty = y;
20 if(board[tx+dx[i]][ty+dy[i]] == 1) /* block immediately */
21 continue;
22 do {
23 tx += dx[i];
24 ty += dy[i];
25 if(is_valid(tx, ty) && board[tx][ty] == 3) { /* end */
26 min = depth+1;
27 return;
28 }
29 } while(is_valid(tx, ty) && board[tx][ty]!=1);
30 if(is_valid(tx, ty)) {
31 board[tx][ty] = 0; /* the block disappears */
32 dfs(depth+1, tx-dx[i], ty-dy[i]);
33 board[tx][ty] = 1;
34 }
35 }
36 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2488思路:
十分熟悉的DFS
需要注意的一點(diǎn)是: 字典序，所以八個(gè)方向的搜索次序不是任意的，從左向右，從上到下，這里定義:
1 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
2 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
另外，我覺得只有從任何一個(gè)點(diǎn)出發(fā)都沒法遍歷，才應(yīng)該輸出impossible
不過(guò)，看了網(wǎng)上的代碼，都只需要從左上角出發(fā)即可得出結(jié)論
代碼:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 struct Item {
3 int x, y;
4 } path[MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col, flag;
7 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
8 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
9
10 void
11 dfs(int depth, int x, int y)
12 {
13 int i, tx, ty;
14 visited[x][y] = 1;
15 path[depth].x = x;
16 path[depth].y = y;
17 if(depth+1 == row*col) {
18 if(!flag) {
19 flag = 1;
20 for(i=0; i<row*col; i++)
21 printf("%c%d", 'A'+path[i].y, path[i].x+1);
22 printf("\n");
23 }
24 }
25 if(!flag) {
26 for(i=0; i<8; i++) {
27 tx = x + dx[i];
28 ty = y + dy[i];
29 if(is_valid(tx, ty) && !visited[tx][ty])
30 dfs(depth+1, tx, ty);
31 }
32 }
33 visited[x][y] = 0;
34 }
35
36 void
37 solve()
38 {
39 int i, j;
40 memset(visited, 0, sizeof(visited));
41 flag = 0;
42 for(i=0; i<row; i++)
43 for(j=0; j<col; j++)
44 if(!flag)
45 dfs(0, i, j);
46 if(!flag)
47 printf("impossible\n");
48 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2251思路:
三維的迷宮
其實(shí)，該題是典型的BFS
不過(guò)由于二維迷宮的影響以及網(wǎng)上題目分類的誤導(dǎo)，開始直接DFS，結(jié)果TLE
值得小慶祝一番的是: 這是AC的第50題(*^__^*) 嘻嘻……，繼續(xù)加油
代碼:
TLE的DFS
1 void
2 dfs(int sl, int sr, int sc, int m)
3 {
4 if(m >= min) /* pruning */
5 return;
6 if(sl==end_l && sr==end_r && sc==end_c) {
7 min = m;
8 return;
9 }
10 int i, tl, tr, tc;
11 for(i=0; i<6; i++) {
12 tl = sl + dl[i];
13 tr = sr + dr[i];
14 tc = sc + dc[i];
15 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
16 visited[tl][tr][tc] = 1;
17 dfs(tl, tr, tc, m+1);
18 visited[tl][tr][tc] = 0;
19 }
20 }
21 }
AC的BFS
1 #define MAX_SIZE 31
2 #define QUEUE_SIZE 100000
3 #define is_valid(l, r, c) (l>=0 && l<level && r>=0 && r<row && c>=0 && c<column)
4 char maze[MAX_SIZE][MAX_SIZE][MAX_SIZE];
5 int visited[MAX_SIZE][MAX_SIZE][MAX_SIZE];
6 int level, row, column;
7 int begin_l, begin_r, begin_c;
8 int end_l, end_r, end_c;
9 /* direction: north, south, west, east, up, down */
10 const int dl[] = {0, 0, 0, 0, -1, 1};
11 const int dr[] = {-1, 1, 0, 0, 0, 0};
12 const int dc[] = {0, 0, -1, 1, 0, 0};
13 struct EACH {
14 int l, r, c;
15 int mins;
16 } queue[QUEUE_SIZE];
17 int head, tail;
18
19
20 void
21 init()
22 {
23 int i, j;
24 char *p;
25 memset(visited, 0, sizeof(visited));
26 memset(queue, 0, sizeof(queue));
27 head = -1;
28 tail = 0;
29 for(i=0; i<level; i++) {
30 for(j=0; j<row; j++) {
31 scanf("%s", maze[i][j]);
32 if((p=strchr(maze[i][j], 'S')) != NULL) {
33 begin_l = i;
34 begin_r = j;
35 begin_c = p-maze[i][j];
36 }
37 if((p=strchr(maze[i][j], 'E')) != NULL) {
38 end_l = i;
39 end_r = j;
40 end_c = p-maze[i][j];
41 }
42 }
43 getchar();
44 }
45 }
46
47 int
48 bfs()
49 {
50 int i, tl, tr, tc, cl, cr, cc, cm;
51 queue[tail].l = begin_l;
52 queue[tail].r = begin_r;
53 queue[tail].c = begin_c;
54 queue[tail].mins = 0;
55 visited[begin_l][begin_r][begin_c] = 1;
56 while(head < tail) {
57 ++head;
58 cl = queue[head].l;
59 cr = queue[head].r;
60 cc = queue[head].c;
61 cm = queue[head].mins;
62 if(cl==end_l && cr==end_r && cc==end_c)
63 return cm;
64 for(i=0; i<6; i++) {
65 tl = cl + dl[i];
66 tr = cr + dr[i];
67 tc = cc + dc[i];
68 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
69 visited[tl][tr][tc] = 1;
70 ++tail;
71 queue[tail].l = tl;
72 queue[tail].r = tr;
73 queue[tail].c = tc;
74 queue[tail].mins = cm+1;
75 }
76 }
77 }
78 return -1;
79 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3126思路:
BFS，一次AC
代碼:
1 #define QUEUE_LEN 10000
2 int from, to;
3 int head, tail;
4 struct EACH {
5 int plen;
6 int num;
7 } queue[QUEUE_LEN];
8 int hash[QUEUE_LEN];
9
10 int
11 is_prime(int num)
12 {
13 int i, up = (int)sqrt(num*1.0);
14 for(i=2; i<=up; i++)
15 if(num%i == 0)
16 return 0;
17 return 1;
18 }
19
20 int
21 bfs()
22 {
23 int cur_plen, cur_num, next_num;
24 int i, j, k, t, div;
25 queue[tail].plen = 0;
26 queue[tail].num = from;
27 hash[queue[tail].num] = 1;
28 while(head < tail) {
29 ++head;
30 cur_plen = queue[head].plen;
31 cur_num = queue[head].num;
32 if(cur_num == to)
33 return cur_plen;
34 div = 1000;
35 t = cur_num;
36 for(i=3; i>=0; i--) {
37 k = t/div;
38 for(j=0; j<=9; j++) {
39 if(i==3 && j==0)
40 continue;
41 next_num = cur_num;
42 next_num -= k*div;
43 next_num += j*div;
44 if(!hash[next_num] && is_prime(next_num)) {
45 ++tail;
46 queue[tail].plen = cur_plen + 1;
47 queue[tail].num = next_num;
48 hash[queue[tail].num] = 1;
49 }
50 }
51 t = t%div;
52 div /= 10;
53 }
54 }
55 return -1;
56 }
// RS Hash Function
unsigned int RSHash( char * str)
{
unsigned int b = 378551 ;
unsigned int a = 63689 ;
unsigned int hash = 0 ;
while ( * str)
{
hash = hash * a + ( * str ++ );
a *= b;
}
return (hash & 0x7FFFFFFF );
}
// JS Hash Function
unsigned int JSHash( char * str)
{
unsigned int hash = 1315423911 ;
while ( * str)
{
hash ^= ((hash << 5 ) + ( * str ++ ) + (hash >> 2 ));
}
return (hash & 0x7FFFFFFF );
}
// P. J. Weinberger Hash Function
unsigned int PJWHash( char * str)
{
unsigned int BitsInUnignedInt = (unsigned int )( sizeof (unsigned int ) * 8 );
unsigned int ThreeQuarters = (unsigned int )((BitsInUnignedInt * 3 ) / 4 );
unsigned int OneEighth = (unsigned int )(BitsInUnignedInt / 8 );
unsigned int HighBits = (unsigned int )( 0xFFFFFFFF ) << (BitsInUnignedInt - OneEighth);
unsigned int hash = 0 ;
unsigned int test = 0 ;
while ( * str)
{
hash = (hash << OneEighth) + ( * str ++ );
if ((test = hash & HighBits) != 0 )
{
hash = ((hash ^ (test >> ThreeQuarters)) & ( ~ HighBits));
}
}
return (hash & 0x7FFFFFFF );
}
// ELF Hash Function
unsigned int ELFHash( char * str)
{
unsigned int hash = 0 ;
unsigned int x = 0 ;
while ( * str)
{
hash = (hash << 4 ) + ( * str ++ );
if ((x = hash & 0xF0000000L ) != 0 )
hash ^= (x >> 24 );
hash &= ~ x;
}
return (hash & 0x7FFFFFFF );
}
// BKDR Hash Function
unsigned int BKDRHash( char * str)
{
unsigned int seed = 131 ; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0 ;
while ( * str)
{
hash = hash * seed + ( * str ++ );
}
return (hash & 0x7FFFFFFF );
}
// SDBM Hash Function
unsigned int SDBMHash( char * str)
{
unsigned int hash = 0 ;
while ( * str)
{
hash = ( * str ++ ) + (hash << 6 ) + (hash << 16 ) - hash;
}
return (hash & 0x7FFFFFFF );
}
// DJB Hash Function
unsigned int DJBHash( char * str)
{
unsigned int hash = 5381 ;
while ( * str)
{
hash += (hash << 5 ) + ( * str ++ );
}
return (hash & 0x7FFFFFFF );
}
// AP Hash Function
unsigned int APHash( char * str)
{
unsigned int hash = 0 ;
int i;
for (i = 0 ; * str; i ++ )
{
if ((i & 1 ) == 0 )
{
hash ^= ((hash << 7 ) ^ ( * str ++ ) ^ (hash >> 3 ));
}
else
{
hash ^= ( ~ ((hash << 11 ) ^ ( * str ++ ) ^ (hash >> 5 )));
}
}
return (hash & 0x7FFFFFFF );
}
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3087思路:
類似于模擬題的BFS，判重使用的是字符串哈希，哈希函數(shù): ELFHash(見PKU 2503)
代碼:
1 int
2 shuffle()
3 {
4 int i, count = 0;
5 int hash_val;
6 memset(hash, 0, sizeof(hash));
7 while(1) {
8 for(i=0; i<2*len; i++) {
9 if(i%2==0)
10 queue[count][i] = tmp2[i/2];
11 else
12 queue[count][i] = tmp1[i/2];
13 }
14 queue[count][i] = '\0';
15 strncpy(tmp1, queue[count], len);
16 strncpy(tmp2, queue[count]+len, len);
17 if(strcmp(queue[count], desire) == 0)
18 return count+1;
19 if(search(queue[count]) != -1)
20 return -1;
21 hash_val = ELFHash(queue[count]);
22 insert(hash_val, count);
23 ++count;
24 }
25 }
問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2503思路:
字符串哈希
這里使用的哈希函數(shù)是ELFHash
1 int ELFHash(char *str)
2 {
3 unsigned long t, hash = 0;
4 while(*str) {
5 hash = (hash<<4) + (*str++);
6 if((t = hash&0xF0000000L))
7 hash ^= t>>24;
8 hash &= ~t;
9 }
10 return (hash & 0x7FFFFFFF)%PRIME;
11 }
因?yàn)橹皩懝１斫鉀Q沖突都是用的鏈接法，這里想嘗試一下開放地址法，采用最簡(jiǎn)單的線性探查，結(jié)果居然TLE
無(wú)奈還是改成鏈接法，然后就AC了
不過(guò)，時(shí)間卻有719MS之多，而網(wǎng)上幾乎相同的代碼只需要230MS左右，不知道是何原因
代碼:
TLE的開放地址法
1 void
2 insert(int hash_val, int index)
3 {
4 if(!hash[hash_val].used) {
5 hash[hash_val].used = 1;
6 hash[hash_val].index = index;
7 } else
8 insert((hash_val+1)%PRIME, index); /* linear probing */
9 }
10
11 int
12 search(char *f_word)
13 {
14 int hash_val = ELFHash(f_word);
15 int i = 0;
16 while(1) {
17 if(!hash[hash_val].used || i==PRIME)
18 break;
19 if(strcmp(f_word, flg[hash[hash_val].index])==0)
20 return hash[hash_val].index;
21 hash_val = (hash_val+1)%PRIME;
22 ++i;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }
AC的鏈接法
1 void
2 insert(int hash_val, int index)
3 {
4 struct Node *node = (struct Node *)malloc(sizeof(struct Node));
5 if(node == NULL) {
6 fprintf(stderr, "malloc error in: insert\n");
7 exit(1);
8 }
9 node->index = index;
10 node->next = hash[hash_val];
11 hash[hash_val] = node;
12 }
13
14 int
15 search(char *f_word)
16 {
17 int hash_val = ELFHash(f_word);
18 struct Node *node = hash[hash_val];
19 while(node != NULL) {
20 if(strcmp(f_word, flg[node->index]) == 0)
21 return node->index;
22 node = node->next;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }