java - 吐出以元音开头并以辅音结尾的字符串的最小和最大子字符串的算法

Question

我正在尝试用 Java 编写这样的算法。我正在测试字符串输入“abaab”。假设字符串输入为小写是安全的。

我无法检查我的算法哪里出错了(它只为这个输入输出“a a”而不是“ab”和“abaab”。有什么想法吗？

static void SmallestAndLargestSubstring(String input) {

        char[] vowels = { 'a', 'e', 'i', 'o', 'u' };
        char[] cons = { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x',
                'y', 'z' };
        char[] charArray = input.toLowerCase().toCharArray();
        int startIndex = 0;
        int shortEndIndex = 0;
        int longEndIndex = 0;
        int large = longEndIndex - startIndex;
        int small = shortEndIndex - startIndex;
        ArrayList<Integer> start = new ArrayList<Integer>();
        ArrayList<Integer> end = new ArrayList<Integer>();

        outerloop: for (int i = 0; i < charArray.length; i++) {
            for (int z = 0; z < vowels.length; z++) {
                if (charArray[i] == vowels[z]) {
                    startIndex = i;
                    start.add(startIndex);
                    if (longEndIndex - startIndex > large) {
                        large = longEndIndex - startIndex;                  
                    }
                    if(longEndIndex - startIndex <= large){
                        shortEndIndex=start.get(start.size()-1);
                    }
                    if (shortEndIndex - startIndex < small) {
                        small = shortEndIndex - startIndex; 
                    }
                    if(shortEndIndex - startIndex >=small){
                        shortEndIndex=start.get(start.size()-1);
                    }


                    continue outerloop;
                }
            }
            for (int j = 0; j < cons.length; j++) {
                if (charArray[i] == cons[j]) {  
                    longEndIndex = i;
                    shortEndIndex = i;
                    end.add(longEndIndex);
                    if (longEndIndex - startIndex > large) {
                        large = longEndIndex - startIndex;
                    }if(longEndIndex - startIndex <= large){
                        longEndIndex=end.get(end.size()-1);
                    }
                    if (shortEndIndex - startIndex < small) {
                        small = shortEndIndex - startIndex;                     
                    }               
                    if(shortEndIndex - startIndex >=small) {
                        shortEndIndex=end.get(end.size()-1);
                    }
                    continue outerloop;
                }
            }
        }


        System.out.println(input.substring(startIndex, shortEndIndex));
        System.out.println(input.substring(startIndex, longEndIndex));
    }

Answer 1

我在寻找同样的问题时偶然发现了这个问题。

THE CURRENTLY ACCEPTED ANSWER IS WRONG.

对于字符串uauubbiox，接受答案中的程序输出:

ub
uauubbiox

这是错误的(正确答案是 auub 和 uubbiox。)即使对于 OP 问题中的情况，该程序也给出了错误答案(abaab 而不是 baab)。

解决这个问题的正确方法是使用 suffix arrays .这是一个伪代码，我相信它会为这个问题产生正确的输出:

given string s as input
sa = suffix_array(s)
savf = the first string in sa which starts with a vowel
smallest substring = savf.substring(0, index of first consonant)

savl = the last string in sa which starts with a vowel
smallest substring = savf.substring(0, index of lastconsonant)

让我们试试这个测试字符串。测试字符串的后缀数组为:

0 auubbiox
1 bbiox
2 biox
3 iox
4 ox
5 uauubbiox
6 ubbiox
7 uubbiox

以元音字母开头的最小字典字符串是:

auubbiox

我们只需要找到这个字符串中以辅音结尾的最小前缀。那将是上述字符串位置 3 处的 b。因此，以元音字母开头辅音字母结尾的字典序最小的字符串是:

auub

对于另一个字符串，查看后缀数组中以元音字母开头的最大字符串。这是索引 7 处的字符串:

uubbiox

因为我们想要尽可能大的字符串，所以我们应该选择尽可能长的以辅音结尾的前缀。在这种情况下，这将是上面的整个字符串。因此，字典序上以元音字母开头并以辅音字母结尾的最大字符串是:

uubbiox

计算字符串的后缀数组可以在 O(n) 中完成。维基百科文章讨论了构建它的一些方法。 Internet 上还有一些聪明的技术，可以使创建一个相对容易编码和实现的技术。我喜欢this one它为后缀数组提供了一种非常直接且易于理解的技术，具有可接受的(对于大多数情况)时间复杂度 O(nlog^2(n))