PKU Judge Online 1936 All in All

■1936 All in All

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

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

□Code

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