Help us understand the problem. What is going on with this article?

最長共通部分列問題

More than 5 years have passed since last update.

アルゴリズムの勉強をしたので、晒します。
問題はコチラ。

2つの文字列S1,S2,...,SnとT1,T2,...,Tmが与えられます。
これら2つの共通部分列の長さの最大値を求めなさい。
ただし、文字列S1,S2,...,Snの部分文字列とは、Si1,Si2,...,Sim(i1<i2<...<im)と表すことができる文字列のことをいいます。

制約:
・1 <= n, m <= 1000

で、私の回答がコチラ。

<?php
class LongSamePartSet
{
    public function calc($firstWords, $secondWords)
    {
        $maxLengths = [];
        for ($i = mb_strlen($firstWords) - 1; $i >= 0; $i--) {
            $selfLengths = [];
            for ($j = mb_strlen($secondWords) - 1; $j >= 0; $j--) {
                if ($firstWords[$i] === $secondWords[$j]) {
                    $length = 0;
                    foreach ($maxLengths as $index => $maxLength) {
                        if ($j < $index && $length < $maxLength) {
                            $length = $maxLength;
                        }
                    }
                    $selfLengths[$j] = $length + 1;
                }
            }
            $maxLengths = $selfLengths + $maxLengths;
        }
        return count($maxLengths) === 0 ? 0 : max($maxLengths);
    }
}

forが3回呼ばれてるので、何か遅そう。。。
会社の先輩のコードは、2回しか呼ばれてませんでした。
SとTを使って、共通部分列をマトリクスで表し、小さい方から順番に求めると・・・うーん、言葉では説明しづらい。
そのうちリファクタしてみようと思います。

【追記】リファクタしました!

class LongestCommonSubsequence
{
    public static function calc($firstWords, $secondWords)
    {
        $note = [];
        for ($i = 0; $i <= mb_strlen($firstWords); $i++) {
            $note[$i] = [];
            if ($i === 0) {
                for ($j = 1; $j <= mb_strlen($secondWords); $j++) {
                    $note[$i][$j] = 0;
                }
                continue;
            }
            $note[$i][0] = 0;
        }

        for ($i = 0; $i < mb_strlen($firstWords); $i++) {
            for ($j = 0; $j < mb_strlen($secondWords); $j++) {
                if ($firstWords[$i] === $secondWords[$j]) {
                    $note[$i + 1][$j + 1] = $note[$i][$j] + 1;
                } else {
                    $note[$i + 1][$j + 1] = max($note[$i][$j + 1], $note[$i + 1][$j]);
                }
            }
            unset($note[$i]);
        }
        return $note[mb_strlen($firstWords)][mb_strlen($secondWords)];
    }
}

【追記】リファクタしました!その2

実は、前回のリファクタは、会社の先輩のコードを真似たものでした。
が、悔しいので、自分自身のコードをリファクタしてみました。
(バグってたので直しました・・←3度目

class LongestCommonSubsequence
{
    public static function calc($firstWords, $secondWords)
    {
        $maxLengths = [];
        for ($i = mb_strlen($firstWords) - 1; $i >= 0; $i--) {
            $checkLengths = [];
            $checkMaxLength = 0;
            for ($j = mb_strlen($secondWords) - 1; $j >= 0; $j--) {
                if (array_key_exists($j + 1, $maxLengths)) {
                    $checkMaxLength = max($checkMaxLength, $maxLengths[$j + 1]);
                }
                $checkLengths[$j] = $checkMaxLength;
            }
            $selfLengths = [];
            for ($j = mb_strlen($secondWords) - 1; $j >= 0; $j--) {
                if ($firstWords[$i] === $secondWords[$j]) {
                    $selfLengths[$j] = $checkLengths[$j] + 1;
                }
            }
            $maxLengths = $selfLengths + $maxLengths;
        }
        return count($maxLengths) === 0 ? 0 : max($maxLengths);
    }
}
ukisoft
まったり developer です。python と js を使うことが多いです。
rymansat
普段は宇宙開発に関わっていないサラリーマンが身近で誰でもできる宇宙開発を実現させることがリーマンサット・プロジェクト(Ryman Sat Project=rsp.)の目的です。キューブサットの開発をはじめ、宇宙を軸として様々なコミュニティやクリエイターとコラボレーションし、民間宇宙開発に関するネットワークを強化、拡張することを目指して活動しています。
https://www.rymansat.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした