英雄会上的一些题

「爱情、让人受尽委屈。」 2022-08-12 09:28 81阅读 0赞

##  ##

## 第五届在线编程大赛月赛指定题目：反向互补子串  [返回首页][Link 1] ##

**题目详情**

这是个字符串问题。我们的字符串只包含大写字母。我们定义一个字母和它13位以后的字母互补。即A与N互补，B与O互补，C与P互补……，我们需要找一个字符串的两个不重叠的子串，其中一个和另外一个的翻转全互补。另外，因为我们的问题来自生物学，所以我们允许这两个字符串的一个可以删掉两个字符（注意：仅允许一个字符串删掉任意位置的两个字符，另外一个必须全部互补上）。我们的目的是求最长的反向互补子串的长度。

输入格式：

多组数据，每组数据一行，有一个字符串。每个字符串长度不超过2000，只有大写英文字母组成。

输出格式：

每组数据输出一行包含一个整数，表示最长的反向互补子串长度。

答题说明

输入样例

ABCD

ABCDQOPN

ABON

输出样例：

解释：

第一个样例，没有互补的子串。

第二个样例，AB和NO互补，所以反向互补子串的时候我们可以选择NPO，删掉一个P即可。

第三个样例，AB与ON反向互补。

//代码仅供参考，请勿抄袭，尊重原创作者AimAtFuture， 3Q
    import java.util.*;
    
    public class ReverseComplementarySubstring{
        public static void main(String[] args) throws Exception{
            Scanner inputer = new Scanner(System.in);     
            while(inputer.hasNext())
            {  
                String str = inputer.next();  
                System.out.println(maxLenOfReverseComplementarySubStr(str));
            }
            inputer.close();    
        }
    
        private static int maxLenOfReverseComplementarySubStr(String str){
            int max_len = 0;
            HashMap<Character, Vector<Integer>> englishAlphabetsHM = convertStr2HM(str);
            Object[] englishAlphabetss = englishAlphabetsHM.keySet().toArray();
            for (int i = 0; i < englishAlphabetss.length; i++){
                if ((Character)englishAlphabetss[i] >= 'N'){
                    continue;
                }
    
                Vector<Integer> englishAlphabetsIndexes = englishAlphabetsHM.get(englishAlphabetss[i]);
                Character hbenglishAlphabets = complementaryEnglishAlphabetsMapFunc((Character)englishAlphabetss[i]);
                Vector<Integer> hbenglishAlphabetsIndexes = englishAlphabetsHM.get(hbenglishAlphabets);
                if (null == hbenglishAlphabetsIndexes){
                    continue;
                }else if (max_len < 1){
                    max_len = 1;
                }
    
                int englishAlphabetsIndexesLen = englishAlphabetsIndexes.size();
                int hbEnglishAlphabetsIndexesLen = hbenglishAlphabetsIndexes.size();
                for (int j = 0; j < englishAlphabetsIndexesLen; j++){
                    int j_index = englishAlphabetsIndexes.get(j);
                    for (int k = 0; k < hbEnglishAlphabetsIndexesLen; k++){
                        int k_index = hbenglishAlphabetsIndexes.get(k);
                        if (k_index-j_index+1>=2*(max_len+1) || j_index-k_index+1>=2*(max_len+1)){
                            if (k_index>j_index){
                                max_len = maxSupLenOfSubString(str, j_index, k_index, max_len);
                            }else{
                                max_len = maxSupLenOfSubString(str, k_index, j_index, max_len);
                            }    
                        }                    
                    }
                }
            }
            return max_len;        
        }
    
        private static int maxSupLenOfSubString(String str, int start_pos, int end_pos, int max_len){
            int condition = (end_pos-start_pos+1)/2;
            while (condition > max_len){
                String strA1 = str.substring(start_pos, start_pos+condition);
                int tmp_index1 = end_pos+1-condition-2;
                if (start_pos+condition > tmp_index1){
                    if (start_pos+condition < end_pos+1-condition-1){
                        tmp_index1 = end_pos+1-condition-1;
                    }else{
                        tmp_index1 = start_pos+condition;
                    }
                }
                String strB1 = str.substring(tmp_index1, end_pos+1);
                if (isComplementTwoString(strA1, strB1)){
                    max_len = condition;
                    break;
                }
                
                int tmp_index2 = start_pos+condition+2;
                if (end_pos+1-condition < tmp_index2){
                    if (end_pos+1-condition > start_pos+condition+1){
                        tmp_index2 = end_pos+1-condition-1;
                    }else{
                        tmp_index2 = end_pos+1-condition;
                    }
                }
                String strA2 = str.substring(start_pos, tmp_index2);
                String strB2 = str.substring(end_pos+1-condition, end_pos+1);
                if (isComplementTwoString(strA2, strB2)){
                    max_len = condition;
                    break;
                }
                condition--;
            }
            
            return max_len;
        }
        
        private static HashMap<Character, Vector<Integer>> convertStr2HM(String str){
            HashMap<Character, Vector<Integer>> ans = new HashMap<Character, Vector<Integer>>();
            int len = str.length();
            for (int i = 0; i < len; i++){
                Vector<Integer> tmp = ans.get(str.charAt(i));
                if (null == tmp){
                    tmp = new Vector<Integer>();
                }
                tmp.add(i);
                ans.put(str.charAt(i), tmp);            
            }
            return ans;
        }
    
        // the different value of the lengths of strA and strB can not more than 2
        private static boolean isComplementTwoString(String strA, String strB){
            boolean ans = true;
    
            if (strB.length() > strA.length()){
                String tmp = strA;
                strA = strB;
                strB = tmp;
            }
    
            int a_len = strA.length();
            int b_len = strB.length();
    
            int max_diff = a_len - b_len;
            int diff = 0;
            for (int i = 0; i < a_len; i++){
                if (b_len-1-i+diff >= 0){
                    if (strA.charAt(i) != complementaryEnglishAlphabetsMapFunc(strB.charAt(b_len-1-i+diff))){
                        diff++;
                    }
                }
    
                if (diff > max_diff){
                    ans = false;
                    break;
                }
            }
    
            return ans;
        }
    
        private static char complementaryEnglishAlphabetsMapFunc(char englishAlphabets){
            char ans = (char)(englishAlphabets + 13);
            if (englishAlphabets - 'A' >= 13){
                ans = (char)(englishAlphabets - 13);
            }
    
            return ans;
        }
    }

[Link 1]: http://hero.csdn.net/