    001    package calhoun.seq;
    002
    003    import calhoun.util.Assert;
    004    import calhoun.util.PrimeUtil;
    005
    006    public class RepeatedSubsequence {
    007
    008            /** Test if infinite repetitions of a and b can be aligned */
    009            public static boolean isRollingMatch(String a, String b) {
    010                    int len = a.length();
    011                    if(len != b.length()) {
    012                            return false;
    013                    }
    014                    if(a.equals(b)) {
    015                            return true;
    016                    }
    017                    StringBuffer sb = new StringBuffer(a);
    018                    for(int i = 1; i<len; ++i) {
    019                            for(int j=0; j<len;++j) {
    020                                    sb.setCharAt(j, a.charAt((i+j)%len));
    021                            }
    022                            if(sb.toString().equals(b)) {
    023                                    return true;
    024                            }
    025                    }
    026                    return false;
    027            }
    028
    029            /** Returns the largest repeated subsequence in a given string. */
    030            public static String calc(String seq) {
    031
    032                    // Pos is the end of the shortest repeat found so far.  starts as being the whole length of the sequence.
    033                    int pos = seq.length();
    034
    035                    // Prime our indexes with the original sequence
    036                    int maxPrime = seq.length()/2+1;
    037
    038                    // Get list of all possible prime factors
    039                    int[] primes = PrimeUtil.primesToAtLeastN(maxPrime);
    040
    041                    // Iterate up the list of primes (start at 2)
    042                    for(int i = 1; primes[i] <= maxPrime; ++i) {
    043                            // While the current repeat length is divisible by the current prime
    044                            while(pos%primes[i] == 0) {
    045                                    boolean repeat = checkRepeat(seq, pos/primes[i], primes[i]);
    046                                    if(repeat) {
    047                                            // If it is identical, choose the first section and attempt to split that
    048                                            pos = pos/primes[i];
    049                                    }
    050                                    else {
    051                                            // If it is not, try the next prime
    052                                            break;
    053                                    }
    054                            }
    055                    }
    056
    057                    String ret = seq.substring(0, pos);
    058                    // Also check for all the same if we got this far
    059                    if(checkRepeat(ret, 1, ret.length())) {
    060                            ret = ret.substring(0,1);
    061                    }
    062
    063                    // Verify results.
    064                    Assert.a(checkRepeat(seq, ret.length(), seq.length()/ret.length()));
    065                    return ret;
    066            }
    067
    068            /** Checks to see if the given sequence begins with n repeats, each of length l. */
    069            public static boolean checkRepeat(String s, int l, int n) {
    070                    for(int i = 0; i<l; ++i) {
    071                            char c = s.charAt(i);
    072                            for(int j = 1; j<n; ++j) {
    073                                    if (c != s.charAt(i+j*l))
    074                                            return false;
    075                            }
    076                    }
    077                    return true;
    078            }
    079    }