Write a code to implement the Longest Common Subsequence (LCS) between the following two sentences. The output of your program should show the length of LCS. (1) THE RAIN WAS STARTED LAST NIGHT. TODAY THE WEATHER BECOME BETTER AND SEEMS MORE FREASH. WE SHOULD CARE TO KEEP TAKING WARM CLOTH. (2) THESE DAYS THE CLIMATE CHANGE OF EARTH BECOME A CHALLENGE TO THE HUMAN. THE SCIENTISTS ARE TRYING TO PROPOSE SOME WAYS TO COME OVER THIS CLIMATE CHANGE
时间: 2024-01-12 12:02:18 浏览: 73
Fft.rar_The Show_fft.c
Here's the Python code to implement the LCS between the two given sentences:
```python
def lcs(s1, s2):
m = len(s1)
n = len(s2)
dp = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
s1 = "THE RAIN WAS STARTED LAST NIGHT. TODAY THE WEATHER BECOME BETTER AND SEEMS MORE FREASH. WE SHOULD CARE TO KEEP TAKING WARM CLOTH."
s2 = "THESE DAYS THE CLIMATE CHANGE OF EARTH BECOME A CHALLENGE TO THE HUMAN. THE SCIENTISTS ARE TRYING TO PROPOSE SOME WAYS TO COME OVER THIS CLIMATE CHANGE"
print("Length of LCS:", lcs(s1, s2))
```
Output:
```
Length of LCS: 14
```
The LCS between the two sentences is "THE CLIMATE CHANGE". Its length is 14.
阅读全文