PKU Judge Online 1936 All in All

■1936 All in All

□Problem
文字列s，tが与えられる．sがtの部分文字列なら"Yes"，そうでなければ"No"を出力せよ．

□Solution
sとtの最長共通部分文字列がsの長さなら"Yes"．

□Code

view plainprint?

1. package p1936;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     final int INF=Integer.MAX_VALUE;  
17.     final double EPS=1e-9;  
18.   
19.     void run(){  
20.         for(; sc.hasNext();){  
21.             String s=sc.next();  
22.             String t=sc.next();  
23.             int m=s.length();  
24.             int n=t.length();  
25.             int[][] dp=new int[n+1][m+1];  
26.             for(int j=0; j<n; j++){  
27.                 for(int i=0; i<m; i++){  
28.                     if(s.charAt(i)==t.charAt(j))  
29.                         dp[j+1][i+1]=dp[j][i]+1;  
30.                     else  
31.                         dp[j+1][i+1]=Math.max(dp[j+1][i], dp[j][i+1]);  
32.                 }  
33.             }  
34.             println(dp[n][m]==m?"Yes":"No");  
35.         }  
36.     }  
37.   
38.     void print(String s){  
39.         System.out.print(s);  
40.     }  
41.   
42.     void println(String s){  
43.         System.out.println(s);  
44.     }  
45.   
46.     public static void main(String[] args){  
47.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
48.         new Main().run();  
49.     }  
50. }  

package p1936;

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    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=0; j<n; j++){
                for(int i=0; i<m; i++){
                    if(s.charAt(i)==t.charAt(j))
                        dp[j+1][i+1]=dp[j][i]+1;
                    else
                        dp[j+1][i+1]=Math.max(dp[j+1][i], dp[j][i+1]);
                }
            }
            println(dp[n][m]==m?"Yes":"No");
        }
    }

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

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

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}