多个字符串中的最长公共子串

Question

    let lcs = (s, t) => {
        let dp = Array.from({ length: s.length + 1 }, () => Array.from({ length: t.length + 1      }, () => 0));
        let maxLen = 0, endIndexS = 0, endIndexT = 0;

        for (let i = 1; i <= s.length; i++) {
            for (let j = 1; j <= t.length; j++) {
                if (s[i - 1] === t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        endIndexS = i;
                        endIndexT = j;
                    }
                }
            }
        }

        if (maxLen === 0) return ''; // If no common subsequence found

        return s.substring(endIndexS - maxLen, endIndexS);
    };

    let args = process.argv.slice(2);
    if (args.length === 0) {
        console.log('');
    } else {
        let result = args[0];
        for (let i = 1; i < args.length; i++) {
            result = lcs(result, args[i]);
            if (result === '') break;
        }
        console.log(result);
    }

我编写了上面的代码，我必须从终端获取输入并打印最长的子字符串..它适用于某些测试用例..但是像这样的测试用例： ZZZABXXX XXXYYYAB ABYYYZZZ 不起作用，因为它应该输出 AB返回空字符串..

Answer 1

你的逻辑是错误的，你在第一对中找到了

ZZZ

，然后就没有进一步的匹配了。 为了解决这样的问题，您应该创建一个后缀树或数组并找到最长的重复/公共子字符串。 这是一个构建树的非常简单的示例（如果需要，请在代码片段中取消注释

console.log()

）：

{
    "Z": {
        "Z": {
            "Z": {
                "A": {
                    "B": {
                        "X": {
                            "X": {
                                "X": {
                                    "string": "ZZZABXXX"
                                }
                            }
                        }
                    }
                },
                "string": "ABYYYZZZ"
            },
            "A": {
                "B": {
                    "X": {
                        "X": {
                            "X": {
                                "string": "ZZZABXXX"
                            }
                        }
                    }
                }
            },
            "string": "ABYYYZZZ"
        },
        "A": {
            "B": {
                "X": {
                    "X": {
                        "X": {
                            "string": "ZZZABXXX"
                        }
                    }
                }
            }
        },
        "string": "ABYYYZZZ"
    },
    "A": {
        "B": {
            "X": {
                "X": {
                    "X": {
                        "string": "ZZZABXXX"
                    }
                }
            },
            "string": "XXXYYYAB",
            "Y": {
                "Y": {
                    "Y": {
                        "Z": {
                            "Z": {
                                "Z": {
                                    "string": "ABYYYZZZ"
                                }
                            }
                        }
                    }
                }
            }
        }
    },
    "B": {
        "X": {
            "X": {
                "X": {
                    "string": "ZZZABXXX"
                }
            }
        },
        "string": "XXXYYYAB",
        "Y": {
            "Y": {
                "Y": {
                    "Z": {
                        "Z": {
                            "Z": {
                                "string": "ABYYYZZZ"
                            }
                        }
                    }
                }
            }
        }
    },
    "X": {
        "X": {
            "X": {
                "string": "ZZZABXXX",
                "Y": {
                    "Y": {
                        "Y": {
                            "A": {
                                "B": {
                                    "string": "XXXYYYAB"
                                }
                            }
                        }
                    }
                }
            },
            "string": "ZZZABXXX",
            "Y": {
                "Y": {
                    "Y": {
                        "A": {
                            "B": {
                                "string": "XXXYYYAB"
                            }
                        }
                    }
                }
            }
        },
        "string": "ZZZABXXX",
        "Y": {
            "Y": {
                "Y": {
                    "A": {
                        "B": {
                            "string": "XXXYYYAB"
                        }
                    }
                }
            }
        }
    },
    "Y": {
        "Y": {
            "Y": {
                "A": {
                    "B": {
                        "string": "XXXYYYAB"
                    }
                },
                "Z": {
                    "Z": {
                        "Z": {
                            "string": "ABYYYZZZ"
                        }
                    }
                }
            },
            "A": {
                "B": {
                    "string": "XXXYYYAB"
                }
            },
            "Z": {
                "Z": {
                    "Z": {
                        "string": "ABYYYZZZ"
                    }
                }
            }
        },
        "A": {
            "B": {
                "string": "XXXYYYAB"
            }
        },
        "Z": {
            "Z": {
                "Z": {
                    "string": "ABYYYZZZ"
                }
            }
        }
    }
}

Then you traverse the tree and find the longest path containing all the strings as leaves. I neither tried to provide the most efficient traversal.
More efficient algorithms exist to build suffix tree/array and find the longest common substring. Just investigate.

function lcs(strings){
  const tree = {};
  for(const str of strings){
      for(let i=0;i<str.length;i++){
        let node = tree;
        for(const c of str.slice(i)){
          node = node[c] ??= {};
        }
        node.string = str;
      }
    
  }
  
  /*console.log(JSON.stringify(tree,(k,v)=>{
    return v instanceof Set ? [...v]: v;
  },4));*/
  
  let result = '';
  
  const traverse = (node, r = '') => {
    const set = new Set;
    for(const c in node){
      if(c === 'string') set.add(node.string);
      else traverse(node[c], r + c).forEach(c => set.add(c))
      if(set.size === strings.length){
        if(r.length > result.length){
          result = r;
        }
      }
    }
    return set;
  }
  
  traverse(tree);
  return result;
}

const args = 'ZZZABXXX XXXYYYAB ABYYYZZZ'.split(' ');

console.log(lcs(args));

.as-console-wrapper{
max-height: 100% !important;
}