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

view plainprint?

1. package p1458;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         for(; sc.hasNext();){  
12.             String s=sc.next();  
13.             String t=sc.next();  
14.             int m=s.length();  
15.             int n=t.length();  
16.             int[][] dp=new int[n+1][m+1];  
17.             for(int j=1; j<=n; j++){  
18.                 for(int i=1; i<=m; i++){  
19.                     if(s.charAt(i-1)==t.charAt(j-1))  
20.                         dp[j][i]=dp[j-1][i-1]+1;  
21.                     else  
22.                         dp[j][i]=Math.max(dp[j-1][i], dp[j][i-1]);  
23.                 }  
24.             }  
25.             println(""+dp[n][m]);  
26.         }  
27.     }  
28.   
29.     void println(String s){  
30.         System.out.println(s);  
31.     }  
32.   
33.     void print(String s){  
34.         System.out.print(s);  
35.     }  
36.   
37.     public static void main(String[] args){  
38.         new Main().run();  
39.     }  
40. }  

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();
    }
}