提问人:Mason Kane 提问时间:11/8/2023 最后编辑:Mason Kane 更新时间:11/8/2023 访问量:49
“O(mn)”就地算法,用于替换文本中的单词重复
An `O(mn)` in-place algorithm to replace a words repeatations in a text
问:
我需要一种算法,将一个字符串作为正文,将另一个字符串作为副文本。该算法应该查找正文中的所有潜台词,并将它们更改为“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)
n
m
我将不胜感激任何帮助!
答: 暂无答案
评论
String[]
O(mn)
String[] words
word
text
text[i - k] = "";
n
m
text
word