需要用*编码字符串中的重复模式，这样*就意味着“从头开始重复”

Question

编码格式：引入*表示“从头开始重复”。实例输入-{a，b，a，b，c，a，b，c，d}可以写成{a，b，*，c，*，d}。产出：5；例2：ABCABCE，输出-5。

这里*表示从头开始重复。例如，如果给定的字符串是ABCABCABCABC，它将返回ABC**，另一个例子是如果字符串是ABCABCABC，它将返回ABC*ABC。

我有下面的代码，但这段代码假设字符串只包含重复模式，没有其他字符，我想修改它以检查：1。哪种模式在重复2。忽略不重复的模式2。根据问题陈述对模式进行编码

import java.util.Scanner;

public class Magicpotion {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the string:");
        String str = sc.nextLine();
        int len = str.length();
        if (len != 0) {
            int lenby3 = len / 3;
            int starcount = ( int).(Math.log(lenby3) / Math.log(2));
            int leftstring = (lenby3 - (int) Math.pow(2, starcount));
            int resultlen = (1 * 3) + starcount + (leftstring * 3);
            System.out.println("ResultLength: " + resultlen);
            System.out.print("ABC");
            for (int i = 0; i < starcount; i++) {
                System.out.print("*");
            }
            for (int i = 0; i < leftstring; i++) {
                System.out.print("ABC");
            }
        } else
            System.out.println("ResultLength: " + 0);
    }
}

在这里，我的假设是ABC将永远是重复模式，因此我将长度除以3。我想概括它，这样我就可以找到重复模式，可以是AB或BC或ABCD，并据此进行。

Answer 1

/**
 * @author mohamed ali
 * https://www.linkedin.com/in/oo0shaheen0oo/
 */

public class Magic_potion_encoding
{
    private static int minimalSteps( String ingredients )
    {
        StringBuilder sb = new StringBuilder(ingredients);

        for(int i =0;i<sb.length();i++)
        {
            char startChar = sb.charAt(i);
            int walkingIndex1=i;
            int startIndex2 =sb.toString().indexOf(startChar,i+1);
            int  walkingIndex2=startIndex2;
            while(walkingIndex2 !=-1 && walkingIndex2<sb.length() && sb.charAt(walkingIndex1) == sb.charAt(walkingIndex2)  )
            {
                if(walkingIndex1+1==startIndex2)
                {
                   String subStringToBeEncoded = sb.substring(i,walkingIndex2+1);//substring the string found and the original "substring does not include the last index hence the +1
                   int matchStartIndex = sb.indexOf(subStringToBeEncoded,walkingIndex2+1);// look for first match for the whole string matched
                   int matchEndeIndex= matchStartIndex+subStringToBeEncoded.length();
                   int origStartIndex=i;
                   int origEndIndex = i+subStringToBeEncoded.length();
                   if (matchStartIndex!=-1 )
                   {
                       if(origEndIndex==matchStartIndex)
                       {
                           sb.replace(matchStartIndex,matchEndeIndex,"*");
                       }
                       else
                       {
                           while(matchStartIndex!=-1 && matchEndeIndex<sb.length() && sb.charAt(origEndIndex) == sb.charAt(matchEndeIndex)  )
                           {
                               if(origEndIndex==matchStartIndex-1)// if the index of the 2 strings are right behind one another
                               {
                                   sb.replace(matchStartIndex,matchEndeIndex+1,"*");
                               }
                               else
                               {
                                   origEndIndex++;
                                   matchEndeIndex++;
                               }
                           }
                       }
                   }
                   sb.replace(startIndex2,walkingIndex2+1,"*");
                   break;
                }
                walkingIndex1++;
                walkingIndex2++;
            }
        }
        System.out.println("orig= " + ingredients + " encoded = " + sb);
        return sb.length();
    }

    public static void main( String[] args )
    {

        if (    minimalSteps("ABCABCE") == 5 &&
                minimalSteps("ABCABCEA") == 6 &&
                minimalSteps("abbbbabbbb") == 5 &&
                minimalSteps("abcde") == 5 &&
                minimalSteps("abcbcbcbcd") == 6 &&
                minimalSteps("ababcababce") == 6 &&
                minimalSteps("ababababxx") == 6 &&
                minimalSteps("aabbccbbccaabbccbbcc") == 8)
        {
            System.out.println( "Pass" );
        }
  else
        {
            System.out.println( "Fail" );
        }
    }
}

Answer 2

• 只需将i-th字符添加到编码中即可。所以长度是ans[i-1]1

最终长度为ans[n-1]。您可以存储如何获得ans[i]以恢复编码本身。检查是否可以编写*可以进行优化，使用一些散列（以获得O（n）解决方案而不是O（n^2））。

与亨利的解决方案不同的是，他总是在可能的情况下应用*。我不清楚它是否会导致最小长度（如果我理解正确，aaaaaa是一个反例），所以我给出了一个确定的解决方案。

Answer 3

这看起来像家庭作业。所以不是完整的解决方案，而是一些提示：

您可以逐个字符地处理输入字符串，并进行编码。如果您在某个时刻已经读取了k个字符，并且下一个k个字符完全相同，则输出一个*，并前进到2k位置。否则，输出下一个输入字符，并将位置提前到k1。

正如dyukha所提到的，这种算法并不总是产生尽可能短的编码。如果需要这样做，则必须在搜索中投入更多的精力。