A Way For Learning

Program on Strings

No comments
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

No comments :

Post a Comment