PKU Judge Online 1458 Common Subsequence

■1458 Common Subsequence

□Problem
文字列sとtのLCS(Longest Common Subsequence:最長共通部分文字列)を求めよ．

□Solution
lcs(i,j)をsのi文字目までの部分文字列とtのj文字目までの部分文字列のLCSとすると，
lcs(i,0)=0
lcs(0,j)=0
lcs(i,j)=lcs(i-1,j-1)+1 (sのi文字目とtのj文字目が等しい場合)
lcs(i,j)=max(lcs(i,j-1),lcs(i-1,j)) (sのi文字目とtのj文字目が等しくない場合)
これらを使ってDP．

□Code

package p1458;

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{
    Scanner sc=new Scanner(System.in);

    void run(){
        for(; sc.hasNext();){
            String s=sc.next();
            String t=sc.next();
            int m=s.length();
            int n=t.length();
            int[][] dp=new int[n+1][m+1];
            for(int j=1; j<=n; j++){
                for(int i=1; i<=m; i++){
                    if(s.charAt(i-1)==t.charAt(j-1))
                        dp[j][i]=dp[j-1][i-1]+1;
                    else
                        dp[j][i]=Math.max(dp[j-1][i], dp[j][i-1]);
                }
            }
            println(""+dp[n][m]);
        }
    }

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }

    public static void main(String[] args){
        new Main().run();
    }
}