原文:
给定两个字符串“x”和“y”，打印最长的公共子字符串的长度。如果两个或多个子字符串中最长的公共子字符串具有相同的值，则打印其中任何一个。
示例:
input : x = "geeksforgeeks",
y = "geeksquiz"
output : geeks
input : x = "zxabcdezy",
y = "yzabcdezx"
output : abcdez
我们讨论了一种求最长公共字符串长度的方法。在这篇文章中，我们已经讨论了打印常用字符串的讨论。
天真的做法:让字符串 x 和 y 分别为长度 m 和 n 。生成所有可能的子串 x ，这需要 0(m2的时间复杂度，并使用 搜索字符串 y 中的每个子串，这可以在 0(n)的时间复杂度中实现。整体时间复杂度为 o(n * m 2 )。
高效途径:是基于帖子里解释的动态编程实现。建立最长后缀矩阵lcsuf[][]，并跟踪具有最大值的单元的索引。让该索引由(行，列)对表示。现在，通过对角遍历lcsuf[][]矩阵，直到 lcsuf[row][col]为止，最终最长的公共子串在该索引的帮助下被构建！= 0，在迭代过程中，从 x[row-1] 或 y[col-1] 中获取字符，并将其从右向左添加到结果公共字符串中。
c
// c implementation to print the longest common substring
#include
#include
#include
using namespace std;
/* function to find and print the longest common
substring of x[0..m-1] and y[0..n-1] */
void printlcsubstr(char* x, char* y, int m, int n)
{
// create a table to store lengths of longest common
// suffixes of substrings. note that lcsuff[i][j]
// contains length of longest common suffix of x[0..i-1]
// and y[0..j-1]. the first row and first column entries
// have no logical meaning, they are used only for
// simplicity of program
int lcsuff[m 1][n 1];
// to store length of the longest common substring
int len = 0;
// to store the index of the cell which contains the
// maximum value. this cell's index helps in building
// up the longest common substring from right to left.
int row, col;
/* following steps build lcsuff[m 1][n 1] in bottom
up fashion. */
for (int i = 0; i <= m; i ) {
for (int j = 0; j <= n; j ) {
if (i == 0 || j == 0)
lcsuff[i][j] = 0;
else if (x[i - 1] == y[j - 1]) {
lcsuff[i][j] = lcsuff[i - 1][j - 1] 1;
if (len < lcsuff[i][j]) {
len = lcsuff[i][j];
row = i;
col = j;
}
}
else
lcsuff[i][j] = 0;
}
}
// if true, then no common substring exists
if (len == 0) {
cout << "no common substring";
return;
}
// allocate space for the longest common substring
char* resultstr = (char*)malloc((len 1) * sizeof(char));
// traverse up diagonally form the (row, col) cell
// until lcsuff[row][col] != 0
while (lcsuff[row][col] != 0) {
resultstr[--len] = x[row - 1]; // or y[col-1]
// move diagonally up to previous cell
row--;
col--;
}
// required longest common substring
cout << resultstr;
}
/* driver program to test above function */
int main()
{
char x[] = "oldsite:geeksforgeeks.org";
char y[] = "newsite:geeksquiz.com";
int m = strlen(x);
int n = strlen(y);
printlcsubstr(x, y, m, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to print the longest common substring
public class longest_common_substr {
/* function to find and print the longest common
substring of x[0..m-1] and y[0..n-1] */
static void printlcsubstr(string x, string y, int m, int n)
{
// create a table to store lengths of longest common
// suffixes of substrings. note that lcsuff[i][j]
// contains length of longest common suffix of x[0..i-1]
// and y[0..j-1]. the first row and first column entries
// have no logical meaning, they are used only for
// simplicity of program
int[][] lcsuff = new int[m 1][n 1];
// to store length of the longest common substring
int len = 0;
// to store the index of the cell which contains the
// maximum value. this cell's index helps in building
// up the longest common substring from right to left.
int row = 0, col = 0;
/* following steps build lcsuff[m 1][n 1] in bottom
up fashion. */
for (int i = 0; i <= m; i ) {
for (int j = 0; j <= n; j ) {
if (i == 0 || j == 0)
lcsuff[i][j] = 0;
else if (x.charat(i - 1) == y.charat(j - 1)) {
lcsuff[i][j] = lcsuff[i - 1][j - 1] 1;
if (len < lcsuff[i][j]) {
len = lcsuff[i][j];
row = i;
col = j;
}
}
else
lcsuff[i][j] = 0;
}
}
// if true, then no common substring exists
if (len == 0) {
system.out.println("no common substring");
return;
}
// allocate space for the longest common substring
string resultstr = "";
// traverse up diagonally form the (row, col) cell
// until lcsuff[row][col] != 0
while (lcsuff[row][col] != 0) {
resultstr = x.charat(row - 1) resultstr; // or y[col-1]
--len;
// move diagonally up to previous cell
row--;
col--;
}
// required longest common substring
system.out.println(resultstr);
}
/* driver program to test above function */
public static void main(string args[])
{
string x = "oldsite:geeksforgeeks.org";
string y = "newsite:geeksquiz.com";
int m = x.length();
int n = y.length();
printlcsubstr(x, y, m, n);
}
}
// this code is contributed by sumit ghosh
python 3
# python3 implementation to print
# the longest common substring
# function to find and print
# the longest common substring of
# x[0..m-1] and y[0..n-1]
def printlcssubstr(x: str, y: str,
m: int, n: int):
# create a table to store lengths of
# longest common suffixes of substrings.
# note that lcsuff[i][j] contains length
# of longest common suffix of x[0..i-1] and
# y[0..j-1]. the first row and first
# column entries have no logical meaning,
# they are used only for simplicity of program
lcsuff = [[0 for i in range(n 1)]
for j in range(m 1)]
# to store length of the
# longest common substring
length = 0
# to store the index of the cell
# which contains the maximum value.
# this cell's index helps in building
# up the longest common substring
# from right to left.
row, col = 0, 0
# following steps build lcsuff[m 1][n 1]
# in bottom up fashion.
for i in range(m 1):
for j in range(n 1):
if i == 0 or j == 0:
lcsuff[i][j] = 0
elif x[i - 1] == y[j - 1]:
lcsuff[i][j] = lcsuff[i - 1][j - 1] 1
if length < lcsuff[i][j]:
length = lcsuff[i][j]
row = i
col = j
else:
lcsuff[i][j] = 0
# if true, then no common substring exists
if length == 0:
print("no common substring")
return
# allocate space for the longest
# common substring
resultstr = ['0'] * length
# traverse up diagonally form the
# (row, col) cell until lcsuff[row][col] != 0
while lcsuff[row][col] != 0:
length -= 1
resultstr[length] = x[row - 1] # or y[col-1]
# move diagonally up to previous cell
row -= 1
col -= 1
# required longest common substring
print(''.join(resultstr))
# driver code
if __name__ == "__main__":
x = "oldsite:geeksforgeeks.org"
y = "newsite:geeksquiz.com"
m = len(x)
n = len(y)
printlcssubstr(x, y, m, n)
# this code is contributed by
# sanjeev2552
c
// c# implementation to print the
// longest common substring
using system;
class gfg {
/* function to find and print the longest common
substring of x[0..m-1] and y[0..n-1] */
static void printlcsubstr(string x, string y, int m, int n)
{
// create a table to store lengths of longest common
// suffixes of substrings. note that lcsuff[i][j]
// contains length of longest common suffix of x[0..i-1]
// and y[0..j-1]. the first row and first column entries
// have no logical meaning, they are used only for
// simplicity of program
int[, ] lcsuff = new int[m 1, n 1];
// to store length of the longest common substring
int len = 0;
// to store the index of the cell which contains the
// maximum value. this cell's index helps in building
// up the longest common substring from right to left.
int row = 0, col = 0;
/* following steps build lcsuff[m 1][n 1] in bottom
up fashion. */
for (int i = 0; i <= m; i ) {
for (int j = 0; j <= n; j ) {
if (i == 0 || j == 0)
lcsuff[i, j] = 0;
else if (x[i - 1] == y[j - 1]) {
lcsuff[i, j] = lcsuff[i - 1, j - 1] 1;
if (len < lcsuff[i, j]) {
len = lcsuff[i, j];
row = i;
col = j;
}
}
else
lcsuff[i, j] = 0;
}
}
// if true, then no common substring exists
if (len == 0) {
console.write("no common substring");
return;
}
// allocate space for the longest common substring
string resultstr = "";
// traverse up diagonally form the (row, col) cell
// until lcsuff[row][col] != 0
while (lcsuff[row, col] != 0) {
resultstr = x[row - 1] resultstr; // or y[col-1]
--len;
// move diagonally up to previous cell
row--;
col--;
}
// required longest common substring
console.writeline(resultstr);
}
/* driver program to test above function */
public static void main()
{
string x = "oldsite:geeksforgeeks.org";
string y = "newsite:geeksquiz.com";
int m = x.length;
int n = y.length;
printlcsubstr(x, y, m, n);
}
}
// this code is contributed by sam007
java 描述语言
output:
site:geeks
时间复杂度: o(mn)。 辅助空间: o(mn)。
空间优化途径: 上解使用的辅助空间为 o(m*n) ，其中 m 和 n 为字符串 x 和 y 的长度，上解使用的空间可以缩减为 o(2*n) 。变量 end 用于存储字符串 x 中最长公共子串的结束点，变量 maxlen 用于存储最长公共子串的长度。
假设当 x 的长度为 i，y 的长度为 j 时，我们处于 dp 状态，其结果存储在 len[i][j]中。 现在如果 x[i-1] == y[j-1]，那么 len[i][j] = 1 len[i-1][j-1] ，即矩阵 len[][]中当前行的结果取决于前一行的值。因此，最长公共子串的所需长度可以通过仅保持两个连续行的值来获得，从而将空间需求减少到 0(2 * n)。
为了打印最长的公共子串，我们使用变量 end。当计算 len[i][j]时，将其与 maxlen 进行比较。如果 maxlen 小于 len[i][j]，则 end 被更新为 i-1，以显示最长公共子串在 x 中的索引 i-1 处结束，maxlen 被更新为 len[i][j]。最长的公共子串是从索引结束–maxlen 1 到 x 中的索引结束。 变量 currrow 用于表示 len[2][n]矩阵的行 0 或行 1 当前用于查找长度。最初，当字符串 x 的长度为零时，第 0 行用作当前行。在每次迭代结束时，当前行成为前一行，前一行成为新的当前行。
下面给出了上述方法的实现:
c
// space optimized cpp implementation to print
// longest common substring.
#include
using namespace std;
// function to find longest common substring.
string lcsubstr(string x, string y)
{
// find length of both the strings.
int m = x.length();
int n = y.length();
// variable to store length of longest
// common substring.
int result = 0;
// variable to store ending point of
// longest common substring in x.
int end;
// matrix to store result of two
// consecutive rows at a time.
int len[2][n];
// variable to represent which row of
// matrix is current row.
int currrow = 0;
// for a particular value of i and j,
// len[currrow][j] stores length of longest
// common substring in string x[0..i] and y[0..j].
for (int i = 0; i <= m; i ) {
for (int j = 0; j <= n; j ) {
if (i == 0 || j == 0) {
len[currrow][j] = 0;
}
else if (x[i - 1] == y[j - 1]) {
len[currrow][j] = len[1 - currrow][j - 1] 1;
if (len[currrow][j] > result) {
result = len[currrow][j];
end = i - 1;
}
}
else {
len[currrow][j] = 0;
}
}
// make current row as previous row and
// previous row as new current row.
currrow = 1 - currrow;
}
// if there is no common substring, print -1.
if (result == 0) {
return "-1";
}
// longest common substring is from index
// end - result 1 to index end in x.
return x.substr(end - result 1, result);
}
// driver code
int main()
{
string x = "geeksforgeeks";
string y = "geeksquiz";
// function call
cout << lcsubstr(x, y);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// space optimized java implementation to print
// longest common substring.
public class gfg {
// function to find longest common substring.
static string lcsubstr(string x, string y) {
// find length of both the strings.
int m = x.length();
int n = y.length();
// variable to store length of longest
// common substring.
int result = 0;
// variable to store ending point of
// longest common substring in x.
int end = 0;
// matrix to store result of two
// consecutive rows at a time.
int len[][] = new int[2][m];
// variable to represent which row of
// matrix is current row.
int currrow = 0;
// for a particular value of i and j,
// len[currrow][j] stores length of longest
// common substring in string x[0..i] and y[0..j].
for (int i = 0; i <= m; i ) {
for (int j = 0; j <= n; j ) {
if (i == 0 || j == 0) {
len[currrow][j] = 0;
} else if (x.charat(i - 1) == y.charat(j - 1)) {
len[currrow][j] = len[1 - currrow][j - 1] 1;
if (len[currrow][j] > result) {
result = len[currrow][j];
end = i - 1;
}
} else {
len[currrow][j] = 0;
}
}
// make current row as previous row and
// previous row as new current row.
currrow = 1 - currrow;
}
// if there is no common substring, print -1.
if (result == 0) {
return "-1";
}
// longest common substring is from index
// end - result 1 to index end in x.
return x.substring(end - result 1, result);
}
// driver code
public static void main(string[] args) {
string x = "geeksforgeeks";
string y = "geeksquiz";
// function call
system.out.println(lcsubstr(x, y));
}
}
// this code is contributed by princiraj1992
python 3
# space optimized python3 implementation to
# print longest common substring.
# function to find longest common substring.
def lcsubstr(x, y):
# find length of both the strings.
m = len(x)
n = len(y)
# variable to store length of longest
# common substring.
result = 0
# variable to store ending point of
# longest common substring in x.
end = 0
# matrix to store result of two
# consecutive rows at a time.
length = [[0 for j in range(m)]
for i in range(2)]
# variable to represent which row of
# matrix is current row.
currrow = 0
# for a particular value of i and j,
# length[currrow][j] stores length
# of longest common substring in
# string x[0..i] and y[0..j].
for i in range(0, m 1):
for j in range(0, n 1):
if (i == 0 or j == 0):
length[currrow][j] = 0
elif (x[i - 1] == y[j - 1]):
length[currrow][j] = length[1 - currrow][j - 1] 1
if (length[currrow][j] > result):
result = length[currrow][j]
end = i - 1
else:
length[currrow][j] = 0
# make current row as previous row and
# previous row as new current row.
currrow = 1 - currrow
# if there is no common substring, print -1.
if (result == 0):
return "-1"
# longest common substring is from index
# end - result 1 to index end in x.
return x[end - result 1 : end 1]
# driver code
if __name__=="__main__":
x = "geeksforgeeks"
y = "geeksquiz"
# function call
print(lcsubstr(x, y))
# this code is contributed by rutvik_56
c
using system;
// space optimized java implementation to print
// longest common substring.
public class gfg {
// function to find longest common substring.
static string lcsubstr(string x, string y) {
// find length of both the strings.
int m = x.length;
int n = y.length;
// variable to store length of longest
// common substring.
int result = 0;
// variable to store ending point of
// longest common substring in x.
int end = 0;
// matrix to store result of two
// consecutive rows at a time.
int[,] len = new int[2,m];
// variable to represent which row of
// matrix is current row.
int currrow = 0;
// for a particular value of i and j,
// len[currrow][j] stores length of longest
// common substring in string x[0..i] and y[0..j].
for (int i = 0; i <= m; i ) {
for (int j = 0; j <= n; j ) {
if (i == 0 || j == 0) {
len[currrow,j] = 0;
} else if (x[i - 1] == y[j - 1]) {
len[currrow,j] = len[1 - currrow,j - 1] 1;
if (len[currrow,j] > result) {
result = len[currrow,j];
end = i - 1;
}
} else {
len[currrow,j] = 0;
}
}
// make current row as previous row and
// previous row as new current row.
currrow = 1 - currrow;
}
// if there is no common substring, print -1.
if (result == 0) {
return "-1";
}
// longest common substring is from index
// end - result 1 to index end in x.
return x.substring(end - result 1, result);
}
// driver code
public static void main() {
string x = "geeksforgeeks";
string y = "geeksquiz";
// function call
console.write(lcsubstr(x, y));
}
}
java 描述语言
output:
geeks
时间复杂度:o(m * n) t3】辅助空间: o(n)
这种方法是由 nik1996 提出的。 本文由阿育什·乔哈里供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
