-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongestRecurringSubSequence.java
More file actions
71 lines (67 loc) · 2.38 KB
/
LongestRecurringSubSequence.java
File metadata and controls
71 lines (67 loc) · 2.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package String;
import java.util.Arrays;
import java.util.Scanner;
public class LongestRecurringSubSequence {
public static int LRS(String s, int i, int j, int t[][]) {
if(i == 0 || j == 0) return 0;
if(t[i-1][j-1] != -1) return t[i-1][j-1];
else if(i-1 != j-1 && s.charAt(i-1) == s.charAt(j-1)) {
//System.out.print(s.charAt(i-1));
t[i-1][j-1] = 1+LRS(s,i-1,j-1,t);
return t[i-1][j-1];
}
else {
t[i-1][j-1] = Math.max(LRS(s,i-1,j,t),LRS(s,i,j-1,t));
return t[i-1][j-1];
}
}
public static int LRSIncre1(String s, int i, int j, int t[][]) {
//System.out.println(s.charAt(i-1) + " " + i + " " + j);
if(i == 0 || j == 0) return 0;
if(t[i][j] != -1) return t[i][j];
else if(i != j && s.charAt(i-1) == s.charAt(j-1)) {
//System.out.println("2--> " + s.charAt(i-1) + " " + i + " " + j);
t[i][j] = 1+LRSIncre1(s,i-1,j-1,t);
return t[i][j];
}
else {
t[i][j] = Math.max(LRSIncre1(s,i-1,j,t),LRSIncre1(s,i,j-1,t));
return t[i][j];
}
}
public static StringBuilder getString(int dp[][], String s) {
int i = s.length(), j = s.length();
StringBuilder sb = new StringBuilder();
while (i>0 && j>0) {
if(i!= j && s.charAt(i-1) == s.charAt(j-1)) {
sb.append(s.charAt(i-1));
//System.out.println(i + " " + j +" "+ s.charAt(i-1));
i--;
j--;
}
else if(dp[i][j-1] > dp[i-1][j]) j--;
else i--;
}
return sb;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- > 0) {
int n = sc.nextInt();
String s = sc.next();
int dp[][] = new int[n+1][n+1];
for(int a[]: dp) Arrays.fill(a, -1);
for(int i=0;i<n+1;i++) {
dp[i][0] = 0;
dp[0][i] = 0;
}
int dp2[][] = new int[n][n];
for(int a[]: dp2) Arrays.fill(a, -1);
//for(int a[]: dp) System.out.println(Arrays.toString(a));
System.out.println(LRSIncre1(s,n,n,dp));
System.out.println(getString(dp, s).reverse());
}
//System.out.println();
}
}