c499 - ♋大耳神下麵真好吃♋

🔗 前往 ZeroJudge 原題

題目描述

題目描述了「大耳神」因為聽到信徒的祈禱詞不清晰而生氣，並會詛咒世界。祈禱詞的清晰度定義為兩個字串的最長共同子字串 (Longest Common Substring) 的長度。題目要求判斷，如果兩個祈禱詞的最長共同子字串長度大於等於給定的閾值 T，則大耳神不會詛咒世界，輸出 "kwa nini unaendesha"；否則，大耳神會詛咒世界，輸出 "sitini na tisa"。

解題思路

本題的核心是計算兩個字串的最長共同子字串的長度。可以使用動態規劃 (Dynamic Programming) 來解決。定義一個二維陣列 lcs[i][j]，表示字串 a 的前 i 個字元和字串 b 的前 j 個字元的的最長共同子字串的長度。

狀態轉移方程如下：

• 如果 a[i] == b[j]，則 lcs[i][j] = lcs[i-1][j-1] + 1
• 如果 a[i] != b[j]，則 lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])

初始化 lcs[i][0] = 0 和 lcs[0][j] = 0。最後，lcs[al-1][bl-1] 就是兩個字串的最長共同子字串的長度。

計算出最長共同子字串的長度後，與給定的閾值 T 比較，即可判斷大耳神是否會詛咒世界。

複雜度分析

• 時間複雜度: O(m*n)，其中 m 和 n 分別是字串 a 和 b 的長度。因為需要遍歷一個 m x n 的二維陣列。
• 空間複雜度: O(m*n)，因為需要使用一個 m x n 的二維陣列來儲存中間結果。

程式碼

#include <iostream>
using namespace std;
int main(){
	string a,b;
	int t;
	while(cin>>a>>b>>t){
		a=' '+a;
		b=' '+b;
		int al=a.length(),bl=b.length(),lcs[al][bl];
		for(int i=0;i<al;++i)
			for(int j=0;j<bl;++j)
				lcs[i][j]=0;
		for(int i=1;i<al;++i){
			for(int j=1;j<bl;++j){
				if(a[i]==b[j])
					lcs[i][j]=lcs[i-1][j-1]+1;
				else
					lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
			}
		}
		if(lcs[al-1][bl-1]>=t)
			cout << "kwa nini unaendesha\n";
		else
			cout << "sitini na tisa\n";
	}
}