111年關務三等資料結構
|
四、以文本 (text) X = “AGTCATTCGATTC”，樣式 (pattern) Y = “ATTC” 兩字串為例，請問使用暴力比較/窮舉法 (exhaustive search) 中的樣式前向法(forward) 及後向法 (backward) 各需比較幾次？（10分） |
答：
暴力比較法實作：
|
#include <iostream> #include <string> using namespace std; int Find(char Text[ ], char Pattern[ ]) { int m, n, T = 0, P = 0, StartT = 0, EndT; // T 指向文字，P 指向 Pattern n = strlen(Text); m = strlen(Pattern); EndT = m-1; int cnt = 0; // 比較次數 while (P < m && StartT <= n-m) { // 當 P = m 時，離開迴圈 cout << "第" << ++cnt << "次比較" << endl; if (Text[T] == Pattern[P]) { P++; T++; } else { StartT++; EndT++; T = StartT; P = 0; } } if (P == m) { return(StartT); // 傳回比對成功的字串開頭索引 } return(-1); } int main( ) { char Text[ ] = "AGTCATTCGATTC"; char Pattern[ ] = "ATTC"; cout << "字串開頭索引是" << Find(Text, Pattern) << endl; return 0; } |
執行結果：
第1次比較
第2次比較
第3次比較
第4次比較
第5次比較
第6次比較
第7次比較
第8次比較
第9次比較
字串開頭索引是4
(一)樣式前向法
[速解]
|
文本 |
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
|
次數 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
－ |
－ |
－ |
－ |
－ |
比較次數 = 2+1+1+1+1+1+1+1 = 9次。
[詳解]
1.第1次比較：
文本：
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
P |
|
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
2.第2次比較：
文本：
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
|
P |
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
3.第3次比較：
文本：
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
P |
|
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
4.第4次比較：
文本：
|
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
P |
|
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
5.第5次比較：
文本：
|
|
|
|
T |
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
P |
|
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
6.第6次比較：
文本：
|
|
|
|
|
T |
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
P |
|
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
7.第7次比較：
文本：
|
|
|
|
|
|
T |
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
|
P |
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
8.第8次比較：
文本：
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
|
|
P |
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
9.第9次比較：
文本：
|
|
|
|
|
|
|
|
T |
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
|
|
|
P |
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
樣式比對結束。
(二)樣式後向法
[速解]
|
文本 |
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
|
次數 |
－ |
－ |
－ |
－ |
－ |
－ |
－ |
－ |
－ |
1 |
1 |
1 |
1 |
比較次數 = 1+1+1+1 = 4次。
[詳解]
1.第1次比較：
文本：
|
|
|
|
|
|
|
|
|
|
|
|
|
T |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
|
|
|
P |
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
2.第2次比較：
文本：
|
|
|
|
|
|
|
|
|
|
|
|
T |
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
|
|
P |
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
3.第3次比較：
文本：
|
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
|
P |
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
4.第4次比較：
文本：
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
G |
T |
C |
A |
T |
T |
C |
G |
A |
T |
T |
C |
樣式：
|
P |
|
|
|
|
0 |
1 |
2 |
3 |
|
A |
T |
T |
C |
樣式比對結束。
留言列表
國考資訊處理解答 (7)
