Мне нужно написать метод, в котором мне задана строка s, и мне нужно вернуть кратчайшую строку, содержащую s, как непрерывную подстроку дважды.
Однако два вхождения s могут перекрываться. Например,
aba возвращает ababaxxxxx возвращает xxxxxxabracadabra возвращает abracadabracadabraМой код до сих пор таков:
import java.util.Scanner;
public class TwiceString {
public static String getShortest(String s) {
int index = -1, i, j = s.length() - 1;
char[] arr = s.toCharArray();
String res = s;
for (i = 0; i < j; i++, j--) {
if (arr[i] == arr[j]) {
index = i;
} else {
break;
}
}
if (index != -1) {
for (i = index + 1; i <= j; i++) {
String tmp = new String(arr, i, i);
res = res + tmp;
}
} else {
res = res + res;
}
return res;
}
public static void main(String args[]) {
Scanner inp = new Scanner(System.in);
System.out.println("Enter the string: ");
String word = inp.next();
System.out.println("The requires shortest string is " + getShortest(word));
}
}
Я знаю, что я, вероятно, ошибаюсь на алгоритмическом уровне, а не на уровне кодирования. Каким должен быть мой алгоритм?
Используйте дерево суффиксов . В частности, после того, как вы построили дерево для s, перейдите к листу, представляющему всю строку, и поднимитесь до тех пор, пока не увидите другой маркер конца строки. Это будет лист самого длинного суффикса, который также является префиксом s.
Как уже говорилось в @phs, часть проблемы может быть переведена на "найти самый длинный префикс s, который также является суффиксом s", и решение без дерева может быть следующим:
public static String getShortest(String s) {
int i = s.length();
while(i > 0 && !s.endsWith(s.substring(0, --i)))
;
return s + s.substring(i);
}
После того, как вы нашли свой индекс и даже если он -1, вам просто нужно добавить к исходной строке подстроку, идущую от index + 1 (так как индекс является последним совпадающим символьным индексом) до конца строки, Там есть метод в String, чтобы получить эту подстроку.
Думаю, вам стоит взглянуть на алгоритм Knuth-Morris-Pratt, таблица частичного соответствия, которую он использует, в значительной степени зависит от того, что вам нужно (и, кстати, это очень хороший алгоритм;)
Если ваша строка ввода s есть, скажем, "abcde", вы можете легко создать регулярное выражение, как показано ниже (обратите внимание, что последний символ "e" отсутствует!):
a(b(c(d)?)?)?$
и запустите его в строке s. Это вернет исходную позицию задней повторяющейся подстроки. Затем вы просто добавили недостающую часть (т.е. Последние N-M символы s, где N - длина s, а M - длина совпадения), например
aba
^ match "a"; append the missing "ba"
xxxxxx
^ match "xxxxx"; append the missing "x"
abracadabra
^ match "abra"; append the missing "cadabra"
nooverlap
--> no match; append "nooverlap"
Из моего понимания вы хотите это сделать:
input: dog
output: dogdog
--------------
input: racecar
output: racecaracecar
Так вот как я бы это сделал:
public String change(String input)
{
StringBuilder outputBuilder = new StringBuilder(input);
int patternLocation = input.length();
for(int x = 1;x < input.length();x++)
{
StringBuilder check = new StringBuilder(input);
for(int y = 0; y < x;y++)
check.deleteCharAt(check.length() - 1);
if(input.endsWith(check.toString()))
{
patternLocation = x;
break;
}
}
outputBuilder.delete(0, input.length() - patternLocation);
return outputBuilder.toString();
}
Надеюсь, это помогло!