任意の数の文字列から最長共通部分文字列を抜き出す

いわゆる最長共通部分文字列問題（LCS）っていうやつです

競技プログラミングなどでは大体2つの文字列が与えられますが、今回は任意の数の文字列からLCSを得る（しかも共通文字列長ではなく共通文字列そのもの）必要があったので、Dartで書きました。

参考になったのはこちらの記事です。一方を固定し、もう一方をずらしながら重ね合わせて最長共通部分文字列を得るアルゴリズムです。

sortByLengthはList<String>を受け取って、文字列長の短い順に並べる関数です。

getLongestCommonSubstring(List<String> list) {
  //共通部分文字列のリスト
  List<String> csList = new List<String>();
  //最長文字列（固定用）
  String base = sortByLength(list).last;
  //ループ処理
  for (int k = 0; k < list.length; k++) {
    String s = list[k];
    //固定文字列と同じなら中断
    if (s == base) {
      continue;
    }
    //固定文字列の前後にダミー挿入
    int length = s.length;
    String dummy = "";
    for (int i = 0; i < length; i++) {
      dummy += "*";
    }
    dummy += base + dummy;
    //現在の2つの文字列の共通部分文字列を取得
    List<String> commons = new List<String>();
    //走査
    for (int i = 0; i < (base.length + s.length); i++) {
      int matchCount = 0;
      int matchStart = 0;
      int tmpCount = 0;
      int tmpStart = 0;
      for (int j = 0; j < s.length; j++) {
        if (s[j] == dummy[i + j]) {
          if (tmpCount == 0) {
            tmpStart = j;
          }
          tmpCount++;
        } else {
          tmpCount = 0;
          tmpStart = 0;
        }
        //最長マッチとマッチ開始位置を更新
        if (tmpCount > matchCount) {
          matchCount = tmpCount;
          matchStart = tmpStart;
        }
      }
      //一致がある場合は部分文字列を抜き出す
      if (matchCount > 0) {
        commons.add(s.substring(matchStart, matchStart + matchCount));
      }
    }
    //走査で見つかったもののうち、共通のものだけを残す
    if (commons.isEmpty) {
      break;
    }
    if (csList.isEmpty) {
      csList.addAll(commons);
    } else {
      csList.removeWhere((String s) => !commons.contains(s));
    }
  }
  if (csList.isEmpty) {
    return "";
  }
  //残った共通部分文字列のうち最も長いものを返す
  return sortByLength(csList).last;
}

Dartで初めて書いたスクリプトがこれなのでDartらしくかけていないと思います（この実装なら大体どの言語でも同じように書けるはず）

計算量はO(m*n^2)って感じでしょうか　

競技プログラミングも普段やらないのでもっと効率がいい方法があるよということであればぜひ教えていただきたいです