Guest User

Untitled

a guest
Jan 15th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.72 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3.  
  4. public class LCS {
  5. public static void main(String[] args)throws Exception{
  6. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  7. f = br.readLine().toCharArray();
  8. s = br.readLine().toCharArray();
  9. fl = f.length;
  10. sl = s.length;
  11. dp = new int[fl][sl];
  12. System.out.println(compute(0,0));
  13. }
  14.  
  15. static int dp[][];
  16. static char[] f, s;
  17. static int fl, sl;
  18.  
  19. public static int compute(int x, int y) {
  20. if(x==fl || y==sl)return 0;
  21.  
  22. if(dp[x][y] != 0)return dp[x][y];
  23. if(f[x] == s[y]) {
  24. return dp[x][y] = 1+compute(x+1, y+1);
  25. }
  26. int max = compute(x+1, y);
  27. max = Math.max(compute(x, y+1), max);
  28. dp[x][y] = max;
  29. return max;
  30. }
  31. }
Add Comment
Please, Sign In to add comment