題目敘述
我們說字串 $A$ 是字串 $B$ 的Prefix（前綴字串），若且唯若字串 $B$ 的前 $len(A)$ 個字母與 $A$ 完全相同，其中 $len(A)$ 指的是字串 $A$ 的長度。例如： “Exam” 和 “Example”都是 “Example” 的 Prefix，但是 “Ample”和 “Exapple” 都不是 “Example” 的 Prefix。同樣的，當 $B$ 的後 $len(A)$ 個字母與 $A$ 完全相同的時候，我們稱 $A$ 是 $B$ 的 Suffix (後綴字串)。給定兩個字串 $P$, $Q$，請你找出最長的字串 $S$ 使得 $S$ 是 $P$ 的 Prefix，同時也是 $Q$ 的 Suffix。
輸入說明
兩個字串 $P$, $Q$ 各佔一行，只包含小寫英文字母，長度皆不超過 1000 字元。
輸出說明
輸出最長的字串 $S$ 的長度 $len(S)$。
Sample Input
example
exam
Sample Output
4
出處
95建中資訊培訓模擬試題一（Prob 2）
OJ連結
題解
注意到輸入的字串長度不超過 1000 個字元，所以我們只要逐一枚舉所有第一個字串的 prefix，看看它是不是第二個字串的 suffix 就好了～
要取出子字 串，可以利用 C++ 的 <string> 函式庫。
/* by tmt514 */
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int main() {
string P, Q;
cin >> P >> Q;
int ans = min(P.size(), Q.size());
while (ans > 0 && (P.substr(0, ans) != Q.substr(Q.size()-ans)))
--ans;
cout << ans << endl;
return 0;
}
關於這題
這題顯然是個字串匹配的問題，而且是 KMP 演算法的直接應用。但是根據輸入規模，找出能夠通過測試的最單純演算法，才是取得先機的關鍵。