Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- public class LCS {
- public static void main(String[] args)throws Exception{
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- f = br.readLine().toCharArray();
- s = br.readLine().toCharArray();
- fl = f.length;
- sl = s.length;
- dp = new int[fl][sl];
- System.out.println(compute(0,0));
- }
- static int dp[][];
- static char[] f, s;
- static int fl, sl;
- public static int compute(int x, int y) {
- if(x==fl || y==sl)return 0;
- if(dp[x][y] != 0)return dp[x][y];
- if(f[x] == s[y]) {
- return dp[x][y] = 1+compute(x+1, y+1);
- }
- int max = compute(x+1, y);
- max = Math.max(compute(x, y+1), max);
- dp[x][y] = max;
- return max;
- }
- }
Add Comment
Please, Sign In to add comment