資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢最長公共子串的長度
假設我們有兩個小寫字串 X 和 Y，我們需要找到它們最長公共子串的長度。
例如，如果輸入 X = "helloworld"，Y = "worldbook"，則輸出為 5，因為 "world" 是最長公共子串，其長度為 5。
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為 m+1 x n+1 的陣列 longest。
len := 0
for i := 0 to m do −
for j := 0 to n do −
if i == 0 or j == 0 then −
longest[i, j] := 0
else if X[i - 1] == Y[j - 1] then −
longest[i, j] := longest[i - 1, j - 1] + 1
if len < longest[i, j] then −
len := longest[i, j]
row := i
col := j
否則
longest[i, j] := 0
返回 len
讓我們來看下面的實現，以便更好地理解：
示例
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
int solve(char* X, char* Y, int m, int n){
int longest[m + 1][n + 1];
int len = 0;
int row, col;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
longest[i][j] = 0;
else if (X[i - 1] == Y[j - 1]) {
longest[i][j] = longest[i - 1][j - 1] + 1;
if (len < longest[i][j]) {
len = longest[i][j];
row = i;
col = j;
}
}
else
longest[i][j] = 0;
}
}
return len;
}
int main(){
char X[] = "helloworld";
char Y[] = "worldbook";
int m = strlen(X);
int n = strlen(Y);
cout << solve(X, Y, m, n);
return 0;
}輸入
"helloworld", "worldbook"
輸出
5
更新於：2020年10月10日
2K+ 瀏覽量
廣告