Program on Strings
Given a string S and a string T, count the number of distinct subsequences of T in S.S = “rabbbit”, T = “rabbit”3.
class Count {
public static int foo(String S, String T) {
//if C[i][j] i means # chars. so C[?][0] === 1
int m = S.length(), n = T.length();
int[][] C = new int[m+1][n+1];
for(int i=0;i<=m;i++) C[i][0] = 1;
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
C[i][j] = C[i-1][j];
if(S.charAt(i-1)==T.charAt(j-1)) C[i][j]+=C[i-1][j-1];
}
}
return C[m][n];
}
public static void main(String[] args) {
System.out.println(foo("rabbbit","rabbit"));
}
}
Reference:
http://www.cs.cmu.edu/~yandongl/distinctseq.html
class Count {
public static int foo(String S, String T) {
//if C[i][j] i means # chars. so C[?][0] === 1
int m = S.length(), n = T.length();
int[][] C = new int[m+1][n+1];
for(int i=0;i<=m;i++) C[i][0] = 1;
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
C[i][j] = C[i-1][j];
if(S.charAt(i-1)==T.charAt(j-1)) C[i][j]+=C[i-1][j-1];
}
}
return C[m][n];
}
public static void main(String[] args) {
System.out.println(foo("rabbbit","rabbit"));
}
}
Reference:
http://www.cs.cmu.edu/~yandongl/distinctseq.html
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment