Problem Statement
We will consider a special genetic recombination called a chromosomal crossover. At the beginning of such a recombination we have two strings of the same length: X and Y. During the chromosomal crossover X and Y will swap their prefixes of the same length. Formally, there will be an integer k between 1 and the length of X, inclusive, with the following property: X will change into Y[0..k-1] + X[k..], and Y will change into X[0..k-1] + Y[k..]. For example, a chromosomal crossover with k = 3 will change the pair "CCCCC", "GGGGG" into the pair "GGGCC", "CCCGG".
Let lcs(X,Y) denote the length of the longest common substring of the strings X and Y. Note that the substring must be contiguous. For example, lcs("CAAA","AAAG") = 3, and lcs("CAC","CTC") = 1. For chromosomes X and Y the value lcs(X,Y) is called their similarity value.
You are given two chromosomes: two equally-long
Definition
- Class:
- ChromosomalCrossover
- Method:
- maximalLength
- Parameters:
- String, String
- Returns:
- int
- Method signature:
- int maximalLength(String A, String B)
- (be sure your method is public)
Constraints
- A will contain between 1 and 50 elements, inclusive.
- A and B will contain the same number of elements.
- Each character in A will be one of {'A', 'T', 'C', 'G'}.
- Each character in B will be one of {'A', 'T', 'C', 'G'}.
Examples
"AAAAAA"
"TCGTCG"
Returns: 3
One optimal solution is to do just a single crossover with k = 3. This produces the chromosomes "TCGAAA" and "AAATCG". Their similarity value is 3 because of the common substring "AAA".
"AAA"
"CCC"
Returns: 2
This time we need to do it twice, first we swap prefix of length 2: ("AAA", "CCC") -> ("CCA", "AAC"). Then we swap prefix of length 1: ("CCA", "AAC") -> ("ACA", "CAC").
"ATCGATCGATCG"
"ATCGATCGATCG"
Returns: 12
This time we don't need to do anything.
"AAAAATTTTTCCCCCGGGGG"
"ACTTCATGTGCTAGCTGTAG"
Returns: 4
"A"
"G"
Returns: 0
"ATCAGGCAATGGACTACTGAGCCAGGTACAT"
"GCTCACGACGAACGGCAGTAACCCCCAGGCT"
Returns: 15
"TTGCCGTGTAGGTCTCGATACCA"
"CGGGACTTAACTCATACACAACG"
Returns: 5
"CACGAGCCGAAGCGGAAT"
"GTGTCCAGTTTGCACTCG"
Returns: 7
"ATCG"
"TTTC"
Returns: 3
"ATGGC"
"GGTAC"
Returns: 3
"GTGGATCATTAGAC"
"TGACTTGGAAATTT"
Returns: 6
"GGTAATACTGGGTAACGGTAGTAAGAGTGTTCTCGATTGG"
"CTTACGGACGATGCCTGGAAGATCCAACCAAGAGGATGAT"
Returns: 14
"TGCTTTAGCAAGCACAGCTTGGCCATTCAGTGA"
"GATCTATTTATCTGGTGCGGGAGAAGTGCCAAT"
Returns: 11
"AGAAGATCCCGAA"
"TGTACGAATAGAA"
Returns: 5
"GGACCGTTGGGATAGGAAGAGTCTTAGGCGGCATTGTCGA"
"GAATAGGAAAGCGCGCGTACATTGTTGGTTTCGGTACTAC"
Returns: 10
"TTCAGAGGAGCATACGGCGAAATCATTCTCTGGTATTAGT"
"TAACACTCACAAGATAGCTCCCTGTCTTGTATTTATTAAT"
Returns: 10
"CT"
"AA"
Returns: 1
"CGCCGCTGCATATCAAA"
"GGCTTTTGGGTAGTGAG"
Returns: 4
"GGTGACTTCGACCATAC"
"ATTGGTGGCTGACTTCT"
Returns: 7
"CCCCTG"
"CATACC"
Returns: 4
"GGATGAACCACCCCGGTTTTCCGCAAAAACCGTATTGAA"
"ACTTCCGGTAGGATAGCGAAGTGCGACGTGTATATCCAC"
Returns: 10
"CACTTCACAAACACACGGCCTCAGAAATGA"
"GAAGCCTCGCCTAATCTTCTTGGTCCCCCG"
Returns: 9
"ACCTCCTCAGGGGGATAGATTTCTATCGATACC"
"TCTGGACCACTATCGCTCTGCACATACATCAAG"
Returns: 14
"GAATGTACCGGGCCGATTGGTGGGCTCTCCGGTTGGA"
"TTTCGTGCCACGGCACCAACACCCAAGTTTGACATAG"
Returns: 10
"AGCATTATGAGCAATCCATTACGAACGTGTATCAAATAGTGTTTGT"
"AACATTCGGGCGCGCGTTTGACCCTCAACCGAACAGGAGCGCAAAA"
Returns: 12
"TTCGTGTCAACTACAT"
"CCGCTACGTCTTACCT"
Returns: 7
"GATAGTA"
"TGACAGC"
Returns: 3
"CACCGCTATTGCCTT"
"AGGTCTCGACGAGGG"
Returns: 6
"ACATGTTAGGCGTTATCCGTGGAACCCGAACAGTTTAAGC"
"GTCTCTAGCATGCGGTTGGTGGTTCGCATTAAAGTATGAC"
Returns: 9
"ATCTGACAC"
"TGCGTGCCC"
Returns: 3
"CGCTTGGCTACATTACCCCCATCGATAATAGTTGGGGCCAGCTCAA"
"ATATTCAGTGAGGTTAAAACGTCTCATGAGATATCCAGGCGCTAAC"
Returns: 12
"GGCATACACCCGATTCGGATTTTAGCATCCTGG"
"CCATGCTTCATCTAGCGGGTGACGTCACGCGCT"
Returns: 13
"GCGGGTCTATCTTCGGTGTCT"
"CAGAGGGCACAATTGGCTCCC"
Returns: 6
"TTTAATGAAAGCACCAGTGCTCCATATGTATCGGTGGTCGC"
"TTACTCGCGGGTCTGTTCAGGAGCTTGTGGTGAATCTATCG"
Returns: 16
"GCTCTGGCCGACT"
"ATACGGCAGGAAC"
Returns: 5
"CAGTATCGCAGATCCCTGAAGAATCCATCAAAAAC"
"GTGACCGTTCTGCCTTGGCTTAAGTAACGCTTACG"
Returns: 9
"TTG"
"GTC"
Returns: 1
"CAC"
"TGT"
Returns: 1
"AGCCACTCGACACGGATTCTATCTT"
"TGTATCTTTATCCATTTTGAATAGA"
Returns: 8
"CCGATACAGTACGGCTTTCATTAGAGCCAGTGAGCGCCT"
"ACGACTGAAGCCGTGCGTGCGTTGTATTACGCACGGCGG"
Returns: 9
"ACTCCCGTATACAGAGTTCTTGAGCAATTCGGAACTTTCGCATAGGTA"
"GTACCTAGACGTTTAGTGTCGGAATGTTTATTCACGAGAGGGAAATAC"
Returns: 12
"TCTTTAAGTATTACCCGAAGCTATAAGTCCCCTC"
"CTGAGATTTGCAGATGGGGATGCGGGAAAGGAAC"
Returns: 14
"AGGCCAGTCTAGCCGG"
"TCATAATGGCATCTAA"
Returns: 7
"AGGCTT"
"GTTTAG"
Returns: 3
"GGCCGTTCAATATCGTGAGCATAGACTGCCAATTGAACTAACGCCATAAT"
"GAACTTGGTAGAGGGCTAGGAATTTACCTGTCTTACTCTGTTCTCAAATC"
Returns: 13
"GTTGATGCTATGAGGTA"
"TCGGAGAGTGCATATAG"
Returns: 6
"GTTATGTATTGGCTAA"
"CTCGTAATGATTCCGA"
Returns: 5
"G"
"A"
Returns: 0
"ACGATGGAAGTAAGAGTAAG"
"CTCCGGCCGTCCGATCCAGT"
Returns: 10
"CCTTTCATTGTCACGATCAGACGCTTATTACAG"
"CTTAGTGTAAGCATGCCGTATGCTGCAAATTGC"
Returns: 10
"GGCACAATGTGGTTGCCAGAGCAACGGTACACCA"
"GTAAGCGTCATGAATTGTAATACTTCGTCTGAGG"
Returns: 11
"CCAAGTGAAGG"
"TTGACACAGCT"
Returns: 5
"GCCGTATAACATTGA"
"AAACACAACGGCTCG"
Returns: 7
"ACTAGGATTGATGGACGGGTTGAACCACGTGTCACCTG"
"AGGAGGCTGACTAGTGGGAGGAACCAGCACTGAACCGC"
Returns: 10
"ACCCCGAATTGTGGTTTCTCATTTTAGCCGGAGCACTCG"
"AACGAGTTGCTCACACTCATCGTATCTACTTGTATAGAT"
Returns: 15
"GAAAAAGAAAGAAAG"
"GGGAAAGAAGAGGAA"
Returns: 9
"GGAAGAAAGGGAAGAGAA"
"GGGAGAAGAAGAGAGAAA"
Returns: 10
"GGGAGAAAAGAAAGAAAAAGGAAGAAAGGG"
"AGAAGAGGAGAAGGAGGGAGAGAGGGAAGG"
Returns: 18
"GAAGAAGGAAGAGGAAGAAGAAAGAA"
"GAAGAGGAGGGGAAGAAGAAGGAAGA"
Returns: 18
"AGGAAGGAGAAGGGAAAGAAGAAAGGGAGGAGGGGAAGGA"
"AGAAGGAAGGAGGAGAGGAAGAAAAGAAGAAAGGAGGGGG"
Returns: 18
"AAGAAGAGGAGGGAGAAG"
"GAAGAAAGAAGAAAGGGG"
Returns: 11
"AAGGAGGGGGGGGAAAGGAGGAAAGAGAAAAAGGG"
"AGGGGGAAAAGAGGAAAAAAAGGGGAAAGGGAGAA"
Returns: 19
"AGGAGAGAAAAGAGGAAGAGGGGAAGGAG"
"GGGAAGAGAAGAGGGAGGAAAGAAAAAAG"
Returns: 14
"AGGAAA"
"AGGGAA"
Returns: 4
"GAAGGAAAAAGGG"
"GAAGGGGGAGGAA"
Returns: 9
"GAGA"
"AGAG"
Returns: 3
"GGAGGAAGGAGAG"
"AAAGGGAAGAAAA"
Returns: 9
"GAAAGGGAGGAAGGAAGGGGA"
"AAAAAAAAAGGAAGAAGGGAG"
Returns: 14
"AGAAAGGGGAAAA"
"AAGGGGAGAAGAA"
Returns: 10
"AAGGAAGAAAAGGAGAGGAGAAGGGGGGAAGAAAGGGGGGGAGGG"
"GAAAAGAGAGAGAAGGAAAAGGAAGGAAAGAGAAGGGAGAAAGGA"
Returns: 28
"AG"
"GG"
Returns: 1
"AGGAAGGAAGAAAGGGAGAAG"
"GGAGAAAGAAAAAAAAGAGGG"
Returns: 17
"GAGGAGGGAGGAAGAAAGAGGAGGGAGAGGAGGGAGGAAAAAGAA"
"AAAAAGAAGAAAGAAAGAAGAGAAAGAAGAGGGAGAGGAGGGGGA"
Returns: 34
"G"
"A"
Returns: 0
"GGGA"
"GAAG"
Returns: 3
"AAGAGAGGAGGGAAGAGGGAAAGAAAGGAAAGAAGGAAAGAG"
"GAAGGGGAAAAAGGAGAAGAGGAAGAAAGGAAGGGAGGGGAG"
Returns: 27
"AAAGAAGAGGAAGGGGGAAGAGGAAGGAGAAG"
"GGGGAAAGAAAGGGAAGAAAGGAAGAAGAGGA"
Returns: 19
"AGGAGAGGAGGAAAAAGGAGGGGGAG"
"AGGGGAAAAGAGGAAAAGGGGAAGAA"
Returns: 14
"GAAAAAGAAAAAGGAGAAGAAGGGGAGGGGGGAGGAGAAAG"
"AGAAGAAAGGAAAAGGAAAAAGGAGGGAGGGGGAGGAGAAG"
Returns: 17
"AGAAAAGAGGGAGAAAAAAAAGGAGGAGGA"
"AAGGGAGAAAGGGAAGGAAAAAGGAGGAAA"
Returns: 16
"GAAGAAAAGGAAAGAGGGAAAGGAGGAGGA"
"AAGAGGAGAGGAAGAAAAAAAAGAGAGAAA"
Returns: 15
"AGAAAGAGAGGAAGGAAGGGGGAAGAAGAAGGAGAAGGAG"
"AGGAAGGAGGGAAAGGGGGGAAAGAGGGGAAAGGGGGGGG"
Returns: 21
"GAAGGAAAGGAAGGAAGGAAGAGAAAAAGGGAAGG"
"GGGAAGAAGAGAGAGGGAGAGGGAGAAAAGGAGAA"
Returns: 23
"AGAGGAGAGGAGGAGAAAGGA"
"GGGGGAGGAGAAAAGAGAGGA"
Returns: 13
"GGAGAAAGGAAAGGAAAAGGGGAGGAAAGGAAAAAGAAAGAAGA"
"AGGAGAGAAGAGAGGAGGAAAAAGGAGGAGGAAGAGAGGAGGGG"
Returns: 29
"GGAAAAGGAAAAGAGGAAGAGAGGGGAAAAGGAGAAGG"
"GGGAAAGAAAGGAGGGGAAAAGAAAGAGAAGAGGGGAA"
Returns: 19
"GAGAGAAGGGGGGA"
"AGGGAGAGGAAAGG"
Returns: 9
"AG"
"GA"
Returns: 1
"GGGGGAAAAGAAGAAGAGAGGGGGAAAAGGAG"
"GAGAGGGGGGGAGAAAGAGGGAAGAGGGAAAG"
Returns: 22
"AAGAAGAAAAAGGGAG"
"GGGAGGGAAGGGGGAG"
Returns: 8
"GAAGAAGAGGGAAGGGAAGGAAGGAGGAAAGAAGGAGGAAG"
"GAGGAAAGAAAGAAGAGAAAGGAGGGAAGAAGAGAAAGGGG"
Returns: 22
"GGAAAAAGGAGAAGGAAGAGAGAAG"
"GGAAAGAGGGGAAAAAAAAAGAGGG"
Returns: 13
"GGGGAGGGGGGAGGGAAGAGAAGAA"
"AGAGGAAAGAAAAAGGGGGGAGGAA"
Returns: 18
"GAAGGAAGGGGAGGGAA"
"GAGAAGGGAGAGAAGGA"
Returns: 13
"GGGAGGG"
"GAGAGAA"
Returns: 5
"AGAAGG"
"GGAGGG"
Returns: 3
"AAGAAGGGGAGAAAGGAGGAGGGAAGGAGAAAGAGAAAAAAAGA"
"AAGAGGAGAAGGAGGGGAGAAGAAGGGAAAGGGAAGAGAAGAAA"
Returns: 22
"AAAAGAAGGGAAGAGAAA"
"GAAGGGGGGGGGGAAGGA"
Returns: 12
"AAAGGAGGAGAAAAGAGAAGGGAG"
"GAAAGAAGGAGGGGAAAAGGGGGG"
Returns: 15
"AAAAAAGGAGGGAAAAAGGAAGAGGGGAAAGAAAGGAAGGGGAGAAA"
"AAAGAGGGGGAAGAGAGGGGAGAGAAAGAGAGAAAAAGAAGGAAAGA"
Returns: 22
"GGGAAAAAGAAGAAGGAAA"
"GAAAGGAGGAAGGAGGAGG"
Returns: 15
"AAGGAGAAAAAAAGGAAAGAGGGGGAGG"
"AGAAAGGAAGGGGGAAGGGGGAAAAGAA"
Returns: 21
"AGGAAGAAAAAAAGAGGAGAGAGAAGAAGGGAAAAGGGAAGGAGGGA"
"GAGGGGGAAAGGAGAGAGAGAGAAGAAAGAGAGGGAGAAGGAAAAAG"
Returns: 32
"GAA"
"AGG"
Returns: 2
"AGGGAGAGAAAAAAGAGGAGGGAAGAAAAGAGGAGGAAAAAGGGGGA"
"AGGAGGGGAAGGGAAGAAAAGGAGGAAGGAAAGGGGAGGAGGAAGGA"
Returns: 19
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
Returns: 46
"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
"ATCGGGCTGTCGTCGATGCTGGGTCGGTCGGTGCTGAGCGTGTCGA"
Returns: 24
"GAGGGGAAGGGAGGGAGAAGAGAAAGAAGAAGGAGAGGGGAAGGGAAGAG"
"TTAATTTTATATTATTATAATTTTAATATATAAATTTTAATTATTTTATT"
Returns: 22
"ATTTCCATCAAACATAACCAATCATTACTTAATCCCCCTACAAAC"
"GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"
Returns: 23
"ACATTTTTTTTTGGG"
"CACCCCTTTTTTTTT"
Returns: 14
"ATGCCTCCCGTTTCGTCTAGAAA"
"GACGGACGCTACAATCTGCGGGA"
Returns: 8
"GACAGTTTGTTTGCACG"
"GCACGCCCGTTTGTTTG"
Returns: 13