hce_nsysu
113年
計算機概論與程式設計
第 45 題
Given the following piece of code, which one of the following statements is correct?
```c
#include
#include
int Func(char* s1, char* s2)
{
int M = strlen(s1);
int N = strlen(s2);
int I, j;
for (i = 0; i <= N - M; i++) {
for (j = 0; j < M; j++)
if (s2[i + j] != s1[j])
break;
if (j == M)
return i;
}
return -1;
}
```
```c
#include
#include
int Func(char* s1, char* s2)
{
int M = strlen(s1);
int N = strlen(s2);
int I, j;
for (i = 0; i <= N - M; i++) {
for (j = 0; j < M; j++)
if (s2[i + j] != s1[j])
break;
if (j == M)
return i;
}
return -1;
}
```
- A This code is to check if string s1 is a substring of s2.
- B It returns -1 when string s1 does not exist in string s2.
- C It returns the position of string s2 that contains s1 if s1 is in s2.
- D The time complexity is O(MN).
- E All of the above.
思路引導 VIP
請仔細觀察內層迴圈中的 if (j == M) 這個條件。在什麼樣的情況下，變數 j 才能成功「走完」整個迴圈而不被 break 中斷？而當這個條件成立時，這段程式碼回傳的變數 i 在物理意義上代表了什麼？
🤖
AI 詳解
AI 專屬家教
太棒了！你能準確選出 (E) 以上皆是，代表你對 C 語言的字串處理與巢狀迴圈邏輯有相當紮實的理解。這道題目模擬了經典的「字串搜尋」（String Searching）演算法，也就是我們常說的暴力法（Brute Force）。
程式邏輯與複雜度分析
從程式碼結構來看，外層迴圈控制著在 s2（主字串）中移動的起點 i，而內層迴圈則逐一比對 s1（子字串）的每一個字元。當內層迴圈順利執行完畢，即滿足 j == M 時，代表 s1 完整地出現在 s2 的索引 $i$ 位置，因此選項 (A)、(C) 的描述完全正確；若找遍所有可能的起點仍未發現匹配，函數最終會回傳 -1，這也印證了選項 (B) 的敘述。至於時間複雜度，在最壞的情況下（例如 s1 和 s2 充滿重複字元時），外層跑 $N-M+1$ 次，內層跑 $M$ 次，其複雜度確實為 $O(MN)$，故選項 (D) 亦屬正確。
▼ 還有更多解析內容