“O(mn)”就地算法,用于替换文本中的单词重复

An `O(mn)` in-place algorithm to replace a words repeatations in a text

提问人:Mason Kane 提问时间:11/8/2023 最后编辑:Mason Kane 更新时间:11/8/2023 访问量:49

问:

我需要一种算法,将一个字符串作为正文,将另一个字符串作为副文本。该算法应该查找正文中的所有潜台词,并将它们更改为“X”。但是如果有两个或两个以上的潜台词并排,它应该只放一个“X”。例如,如果正文是 abababccab,副文本是 ab,则输出应为 XccX。所有的 s 都替换为“X”,但由于开始时有两个腹肌,所以我们在那里只有一个“X”。此外,该算法不应使用额外的内存空间(O(1)表示内存空间)。ab

我用 Java 编写了以下代码:

import java.util.Scanner;

public class DS_Replace {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] text = scanner.next().split("");
        String[] word = scanner.next().split("");
        DSReplace(text, word);
        for (String s : text) {
            System.out.print(s);
        }
        System.out.println();
    }

    private static void DSReplace(String[] text, String[] word) {
        int n = text.length;
        int m = word.length;
        outerLoop:
        for (int i = 0; i < n; i++) {
            int count = 0;
            if (text[i].equals(word[0])) {
                whileLoop:
                while (true) {
                    for (int j = 0; j < m; j++) {
                        if (i + j + 1 > n)
                            break whileLoop;
                        if (!text[i + j].equals(word[j])) {
                            if (count == 0)
                                continue outerLoop;
                            else
                                break whileLoop;
                        }
                    }
                    count++;
                    i += m;
                }
                for (int k = 1; k <= m * count; k++) {
                    if (k != 1)
                        text[i - k] = "";
                    else
                        text[i - k] = "X";
                }
            }
        }
    }
}

我认为这个算法的时间复杂度是正文的长度,是特定子字符串的长度。我对时间复杂度的看法正确吗?你知道有什么更好的方法来编写代码吗?O(mn)nm

我将不胜感激任何帮助!

Java 字符串 算法 取代了 时间复杂度

评论

0赞 rzwitserloot 11/8/2023
您的参数类型与所述的问题不一致。如前所述,问题涉及单个文本(但您的方法接受字符串数组)。如前所述,这个问题是关于寻找一根针。但是您的代码使用 .因此,你的问题毫无意义,任何关于m 和 n 的讨论都需要说明 m 和 n 是什么。它们是元素的数量吗?每个“单词”元素的平均长度?String[]O(mn)String[] words
0赞 Mason Kane 11/8/2023
@rzwitserloot 哦,对不起,和数组的每个元素都是一个字符。我没有使用 char 原始类型,因为行 . 是文本的长度,也是单词的长度。和 都是字符数组(换句话说,字符串)。我刚刚编辑了代码!谢谢。wordtexttext[i - k] = "";nmtextword

答: 暂无答案