Привет!
Я написал рекурсивный алгоритм сравнения с нуля.Он находит «наилучшее совпадение» между двумя строками, так что различия минимизируются, и выводит эти две строки с любыми различиями, представленными в CAPS.Он отлично работает "как есть", за исключением того, что он довольно неэффективен.Я смотрю на это уже полтора дня, пытаясь найти способы сделать его итеративным или, по крайней мере, уменьшить глубину стека, которого он достигает, но я нахожусь в своем уме и надеялся, что острый ум здесьбудет видеть решение более четко, чем я.
Ниже приведено описание кода.Класс MergePoint, на который ссылаются, является простым узлом стиля «связанный список», который содержит целое число «индекс в исходном», целое число «индекс в измененном» и «следующий» MergePoint.Список MergePoint представляет серию индексов в каждом массиве, которые были «объединены».Когда цепочка завершена, любые индексы, которые не представлены в цепочке, являются вставками / удалениями.Объект NullObject является расширением MergePoint, которое, если вспомнить его, не было абсолютно необходимым для создания и в принципе может считаться обычным «нулевым».
Любые советы / предложения будут очень высоко оценены.
public class StringCompare
{
public static int[][] mergeList = new int[0][0];
public static MergePoint NULL = NullObject.getNull();
public static int maxMerged = 0;
public static int minClusterSize = -1;
public static void diff(String orig, String alt)
{
String[] original = orig.toUpperCase().split(" ");
String[] altered = alt.toUpperCase().split(" ");
for(int i = 0; i < altered.length; i++)
{
merge(original, altered, 0, i, NULL, NULL, 0, 0);
}
for(int i = 0; i < mergeList.length; i++)
{
or[mergeList[i][0]] = or[mergeList[i][0]].toLowerCase();
al[mergeList[i][1]] = al[mergeList[i][1]].toLowerCase();
}
printStringArray(or);
printStringArray(al);
}
private void printStringArray(String[] arr)
{
for(String word : arr)
{
System.out.print(word.trim() + " ");
}
System.out.println();
}
private static void merge(String[] original, String[] altered, int indexInOriginal, int indexInAltered, MergePoint head, MergePoint tail, int listSize, int clusters)
{
if (indexInOriginal >= original.length)
{
if (listSize > 0)
{
if (((listSize == maxMerged) && (clusters < minClusterSize)) ||
(listSize > maxMerged))
{
storeMergePoints(head, listSize, clusters);
}
}
}
else if (indexInAltered >= altered.length)
{
if (tail != NULL)
{
merge(original, altered, (indexInOriginal + 1), (tail.indexInNew() + 1), head, tail, listSize, clusters);
}
else
{
merge(original, altered, (indexInOriginal + 1), 0, head, tail, listSize, 0);
}
}
else
{
if(original[indexInOriginal].equals(altered[indexInAltered]))
{
MergePoint mergePoint = new MergePoint(indexInOriginal, indexInAltered);
MergePoint bookMark = NULL;
int newClusters = clusters;
if (indexInOriginal != (tail.indexInOriginal() + 1))
{
newClusters++;
}
if (indexInAltered != (tail.indexInNew() + 1))
{
newClusters++;
}
if (head == NULL)
{
head = mergePoint;
tail = head;
}
else
{
tail.setNext(mergePoint);
bookMark = tail;
tail = tail.next();
}
merge(original, altered, (indexInOriginal + 1), (indexInAltered + 1), head, tail, (listSize + 1), newClusters);
if (bookMark == NULL)
{
merge(original, altered, indexInOriginal, (indexInAltered + 1), NULL, NULL, 0, 0);
}
else
{
bookMark.setNext(NULL);
merge(original, altered, indexInOriginal, (indexInAltered + 1), head, bookMark, listSize, newClusters);
}
}
else
{
merge(original, altered, indexInOriginal, (indexInAltered + 1), head, tail, listSize, clusters);
}
}
}
public static void storeMergePoints(MergePoint current, int size, int clusters)
{
mergeList = new int[size][2];
maxMerged = size;
minClusterSize = clusters;
for(int i = 0; i < size; i++)
{
mergeList[i][0] = current.indexInOriginal();
mergeList[i][1] = current.indexInNew();
current = current.next();
}
}
}