java - 最短超弦

我写了一些代码，该代码从值数组中计算出最短的超字符串。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;



public class ShortestCommonSuperstringAlgorithm {

private void createSuperString(Set<String> subStrings) {
    int totalStrings = subStrings.size();
    String[] match = new String[totalStrings];
    int i = 0;

    for(String superString : subStrings) {

        Set<String> temp = new HashSet<String>(subStrings);
        String maxSuperString = superString;
        while(temp.size() > 1) {

            String subString = "";
            String nextMaxSuperString = maxSuperString;

            for(String nextString : temp) {

                if(!nextString.equals(nextMaxSuperString)) {

                    String superTemp = getSuperString(maxSuperString, nextString);
                    if (nextMaxSuperString.equals(maxSuperString) || nextMaxSuperString.length() > superTemp.length()) {
                        nextMaxSuperString = superTemp;
                        subString = nextString;
                    }
                }
            }

            temp.remove(maxSuperString);
            temp.remove(subString);
            maxSuperString = nextMaxSuperString;
            temp.add(maxSuperString);
        }

        match[i] = maxSuperString;
        //System.out.println(match[i]);
        i++;
    }

    String bestAns = match[0];

    for(i = 1; i < match.length; i++) {
        if(bestAns.length() > match[i].length()) {
            bestAns = match[i];
        }
    }

    System.out.println("Shortest Common Super String => " + bestAns);
    System.out.println("With a Length of             => " + bestAns.length());

}

private String getSuperString(String superString, String someString) {
    String result = superString;

    int endIndex = someString.length() - 1;

    while(endIndex > 0 && !superString.endsWith(someString.substring(0, endIndex)))  {
        endIndex--;
    }

    if(endIndex > 0) {
        result += someString.substring(endIndex);
    }
    else {
        result += someString;
    }

    return result;
}

public static void main(String arg[]) {

    Set<String> fragments = new HashSet<String>();
    ShortestCommonSuperstringAlgorithm superStringCreator = new ShortestCommonSuperstringAlgorithm();

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = "";
    int noOfFragments = 0;      // noOfFragments = m

    // read input string, no. of fragments and their length

    try{
        System.out.println("Enter the no of Fragments : ");
        noOfFragments = Integer.parseInt(br.readLine());

        int size = 1;
        do{
            System.out.println(size + ". Fragment String : ");
            input = br.readLine();
            fragments.add(input);
            size++;
        }while(size<=noOfFragments);

    }catch(Exception ex){
        System.out.println("Please give correct Inputs.");
        ex.printStackTrace();
        return;
    }

    // find the shortest superstring
    superStringCreator.createSuperString(fragments);
    }
}

我需要计算的是可以串联以创建最短超字符串的数组元素的最小数量。

例如，代码当前的工作方式如下。

Input array: s[0] = ada
s[1] = dab
s[2] = dba
s[3] = adb
s[4] = bad
s[5] = bda
Shortest Common Super String => adbadabda

我需要计算的额外输出看起来像这样

Solution = s[3]+s[0]+s[5]

任何帮助将非常感激!

最佳答案

正如我评论的那样，您的算法仅能找到和近似最短的超字符串。正确的算法(但速度要慢得多)大致如下所示:

初始化best_permutation = null和shortest_size =无限

计算子字符串序列的所有排列(例如，使用堆算法)

对于每个排列，将邻居尽可能多地“挤压”在一起

如果结果大小小于shortest_size，则将新值分配给shortest_size和best_permutation

在该算法的最后，您将具有best_permutation以输出要打印的内容。

对于您的近似算法，创建一个自定义类CombinedString来记住它“吞咽”了哪些子字符串可能是最简单的。

喜欢

class CombinedString {
   final String combinedValue;
   final String[] substrings;
   final int[] substringPositions;

   public CombinedString(String initial) {
       combinedValue = initial;
       substrings = {initial};
       substringPositions = [0]; // first string inserted at position 0
   }

   public CombinedString(CombinedString left, CombinedString right) {
       // ...
   }

   // ...
}

然后你的方法签名会像

private CombinedString getSuperString(CombinedString superString, CombinedString someString)

最后的结果将是CombinedString，从中可以轻松产生所需的输出。

关于java - 最短超弦，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48963201/