8

タスクは、任意の 2 つの一意の繰り返し文字で構成される特定の文字列内で最長の部分文字列を見つけることです
。入力文字列「aabadefghaabbaagad」では、そのような最長の文字列は「aabbaa」です

次の解決策を思いつきましたが、同じことを行うより効率的な方法があるかどうかを確認したかったのです

import java.util.*; 

public class SubString {
    public static void main(String[] args) { 
    //String inStr="defghgadaaaaabaababbbbbbd";
    String inStr="aabadefghaabbaagad";
    //String inStr="aaaaaaaaaaaaaaaaaaaa";
    System.out.println("Input string is         "+inStr);

    StringBuilder sb = new StringBuilder(inStr.length());
    String subStr="";
    String interStr="";
    String maxStr="";
    int start=0,length=0, maxStart=0, maxlength=0, temp=0;

    while(start+2<inStr.length())   
    {    int i=0;
         temp=start;
         char x = inStr.charAt(start);
         char y = inStr.charAt(start+1);
         sb.append(x);
         sb.append(y);

         while( (x==y) && (start+2<inStr.length()) )
         {    start++;
              y = inStr.charAt(start+1);
              sb.append(y);
         }

         subStr=inStr.substring(start+2);
         while(i<subStr.length())
         {    if(subStr.charAt(i)==x || subStr.charAt(i)==y )
              {    sb.append(subStr.charAt(i));
                   i++;
              }
              else
                   break;
         }

         interStr= sb.toString();
         System.out.println("Intermediate string "+ interStr);
         length=interStr.length();
         if(maxlength<length)
         {    maxlength=length;
              length=0;
              maxStr = new String(interStr);
              maxStart=temp;
         }

         start++;
         sb.setLength(0);
   }

   System.out.println("");
   System.out.println("Longest string is "+maxStr.length()+" chars long "+maxStr);  
}
}
4

7 に答える 7

9

線形時間アルゴリズムに導くかもしれないヒントを次に示します (これは宿題だと思いますので、全体の解決策は示しませんx) y。まで戻ってstart + 1検索をやり直す必要はありません。文字列を取りましょうaabaaddaa。見た時点でaabaa次の文字がdである場合、インデックス 1 または 2 で検索を再開しても意味がありません。これらの場合、再度ヒットする前にabaaorしか得られないからです。実際のところ、インデックス 3 ( s の最後のグループの最初のインデックス)に直接移動できます。baadstartaadi、インデックス 5 に移動して続行できます。

編集：以下の疑似コード。

// Find the first letter that is not equal to the first one, 
// or return the entire string if it consists of one type of characters
int start = 0;
int i = 1;
while (i < str.length() && str[i] == str[start])
    i++;
if (i == str.length())
    return str;

// The main algorithm
char[2] chars = {str[start], str[i]};
int lastGroupStart = 0;
while (i < str.length()) {
    if (str[i] == chars[0] || str[i] == chars[1]) {
        if (str[i] != str[i - 1])
            lastGroupStart = i;
    }
    else {
        //TODO: str.substring(start, i) is a locally maximal string; 
        //      compare it to the longest one so far
        start = lastGroupStart;
        lastGroupStart = i;
        chars[0] = str[start];
        chars[1] = str[lastGroupStart];
    }
    i++;
}
//TODO: After the loop, str.substring(start, str.length()) 
//      is also a potential solution.
于 2013-02-21T10:43:05.453 に答える
0 
import java.util.ArrayList;
import java.util.Collections; 
import java.util.HashMap; import java.util.Iterator; import java.util.List;
import java.util.Map;

public class PrintLLargestSubString {

    public static void main(String[] args){         String string =
            "abcdefghijklmnopqrstuvbcdefghijklmnopbcsdcelfabcdefghi";
    List<Integer> list = new ArrayList<Integer> ();         List<Integer>
    keyList = new ArrayList<Integer> ();        List<Integer> Indexlist = new
    ArrayList<Integer> ();      List<Integer> DifferenceList = new
    ArrayList<Integer> ();      Map<Integer, Integer> map = new
    HashMap<Integer, Integer>();        int index = 0;      int len = 1;        int
    j=1;        Indexlist.add(0);       for(int i = 0; i< string.length() ;i++) {
        if(j< string.length()){
            if(string.charAt(i) < string.charAt(j)){
                len++;
                list.add(len);
            } else{
                index= i+1;
                Indexlist.add(index); //                    System.out.println("\nindex" + index);              
                len=1;              
            }           }           j++;        } //        System.out.println("\nlist" +list);         System.out.println("index List" +Indexlist); //     int n =
    Collections.max(list); //       int ind = Collections.max(Indexlist);
    //      System.out.println("Max number in IndexList  " +n);
    //      System.out.println("Index Max is " +ind);

    //Finding max difference in a list of elements      for(int diff = 0;
    diff< Indexlist.size()-1;diff++){           int difference =
            Indexlist.get(diff+1)-Indexlist.get(diff);
    map.put(Indexlist.get(diff), difference);
    DifferenceList.add(difference);         }
    System.out.println("Difference between indexes" +DifferenceList); //        Iterator<Integer> keySetIterator = map.keySet().iterator(); //      while(keySetIterator.hasNext()){
    //          Integer key = keySetIterator.next();
    //          System.out.println("index: " + key + "\tDifference  "
    +map.get(key)); // //       } //        System.out.println("Diffferenece List" +DifferenceList);        int maxdiff = Collections.max(DifferenceList);      System.out.println("Max diff is " + maxdiff);       //////      Integer
    value = maxdiff;        int key = 0;        keyList.addAll(map.keySet());
    Collections.sort(keyList);      System.out.println("List of al keys"
            +keyList); //       System.out.println(map.entrySet());         for(Map.Entry entry: map.entrySet()){           if(value.equals(entry.getValue())){
    key =  (int) entry.getKey();            }       }       System.out.println("Key value of max difference starting element is " + key);   

    //Iterating key list and finding next key value         int next = 0 ;
    int KeyIndex = 0;       int b;      for(b= 0; b<keyList.size(); b++) {
        if(keyList.get(b)==key){
            KeyIndex = b;           }                       }       System.out.println("index of key\t" +KeyIndex);         int nextIndex = KeyIndex+1;         System.out.println("next Index = " +nextIndex);         next = keyList.get(nextIndex);
            System.out.println("next Index value is = " +next);

            for( int z = KeyIndex; z < next ; z++) {
                System.out.print(string.charAt(z));         }   }

            }
于 2015-07-04T23:50:50.703 に答える