在Javascript中查找字符串之间的区别
我想比较两个字符串（之前和之后）并检测它们之间的确切位置和变化。
对于任何改变，我想知道：
假设字符串一次只能在一个地方变化（例如，从不“ B il l ” - >“ K il n ”）。
另外，我需要开始和结束位置来反映变化的类型：
例如：
"0123456789" -> "03456789"
Start: 1, End: 2, Change: "" (deletion)
"03456789" -> "0123456789"
Start: 1, End: 1, Change: "12" (insertion)
"Hello World!" -> "Hello Aliens!"
Start: 6, End: 10, Change: "Aliens" (replacement)
"Hi" -> "Hi"
Start: 0, End: 0, Change: "" (no change)
我能够在某种程度上检测到已更改文本的位置，但它在所有情况下都不起作用，因为为了准确执行此操作，我需要知道进行了哪种更改。
var OldText = "My edited string!";
var NewText = "My first string!";
var ChangeStart = 0;
var NewChangeEnd = 0;
var OldChangeEnd = 0;
console.log("Comparing start:");
for (var i = 0; i < NewText.length; i++) {
console.log(i + ": " + NewText[i] + " -> " + OldText[i]);
if (NewText[i] != OldText[i]) {
ChangeStart = i;
break;
}
}
console.log("Comparing end:");
// "Addition"?
if (NewText.length > OldText.length) {
for (var i = 1; i < NewText.length; i++) {
console.log(i + "(N: " + (NewText.length - i) + " O: " + (OldText.length - i) + ": " + NewText.substring(NewText.length - i, NewText.length - i + 1) + " -> " + OldText.substring(OldText.length - i, OldText.length - i + 1));
if (NewText.substring(NewText.length - i, NewText.length - i + 1) != OldText.substring(OldText.length - i, OldText.length - i + 1)) {
NewChangeEnd = NewText.length - i;
OldChangeEnd = OldText.length - i;
break;
}
}
// "Deletion"?
} else if (NewText.length < OldText.length) {
for (var i = 1; i < OldText.length; i++) {
console.log(i + "(N: " + (NewText.length - i) + " O: " + (OldText.length - i) + ": " + NewText.substring(NewText.length - i, NewText.length - i + 1) + " -> " + OldText.substring(OldText.length - i, OldText.length - i + 1));
if (NewText.substring(NewText.length - i, NewText.length - i + 1) != OldText.substring(OldText.length - i, OldText.length - i + 1)) {
NewChangeEnd = NewText.length - i;
OldChangeEnd = OldText.length - i;
break;
}
}
// Same length...
} else {
// Do something
}
console.log("Change start: " + ChangeStart);
console.log("NChange end : " + NewChangeEnd);
console.log("OChange end : " + OldChangeEnd);
console.log("Change: " + OldText.substring(ChangeStart, OldChangeEnd + 1));
如何判断是否进行了插入，删除或替换？
我搜索了一些其他类似的问题，但他们似乎没有帮助。
我已经通过你的代码，你的匹配字符串的逻辑对我来说很有意义。 它记录ChangeStart ， NewChangeEnd和OldChangeEnd正确的算法流程好吗。 你只是想知道是否发生插入 ， 删除或替换 。 以下是我将如何去做。
首先，你需要确保你有不匹配，即先点后ChangeStart当你然后遍历从最终的字符串，该指数不应该越过ChangeStart 。
我会给你一个例子。 考虑以下字符串：
var NewText = "Hello Worllolds!";
var OldText = "Hello Worlds!";
ChangeStart -> 10 //Makes sense
OldChangeEnd -> 8
NewChangeEnd -> 11
console.log("Change: " + NewText.substring(ChangeStart, NewChangeEnd + 1));
//Ouputs "lo"
在这种情况下，问题是当它从后面开始匹配时，流程如下所示：
Comparing end:
1(N: 12 O: 12: ! -> !)
2(N: 11 O: 11: s -> s)
3(N: 10 O: 10: d -> d) -> You need to stop here!
//Although there is not a mismatch, but we have reached ChangeStart and
//we have already established that characters from 0 -> ChangeStart-1 match
//That is why it outputs "lo" instead of "lol"
假设，我刚刚说的是有道理的，你只需要修改你的for循环，就像这样：
if (NewText.length > OldText.length) {
for (var i = 1; i < NewText.length && ((OldText.length-i)>=ChangeStart); i++) {
...
NewChangeEnd = NewText.length - i -1;
OldChangeEnd = OldText.length - i -1;
if(//Mismatch condition reached){
//break..That code is fine.
}
}
这个条件 - > (OldText.length-i)>=ChangeStart负责我提到的异常，因此如果达到这个条件， for循环会自动终止。 但是，就像我刚才所说的那样，在遇到错误匹配之前可能会遇到这种情况，就像我刚刚演示的那样。 因此，您需要将NewChangeEnd和OldChangeEnd值更新为小于匹配值的1。 如果出现不匹配情况，请适当存储这些值。
取而代之的是else -if我们知道NewText.length > OldText.length绝对不是真的，也就是说它可以是替换或删除，那么我们可以将这两个条件包装起来。 再次NewText.length > OldText.length也意味着它可能是一个替换或插入按您的例子，这是有道理的。 所以else可能是这样的：
else {
for (var i = 1; i < OldText.length && ((OldText.length-i)>=ChangeStart); i++) {
...
NewChangeEnd = NewText.length - i -1;
OldChangeEnd = OldText.length - i -1;
if(//Mismatch condition reached){
//break..That code is fine.
}
}
如果你已经理解到目前为止的细微变化，确定具体的案例非常简单：
ChangeStart > NewChangeEnd 。 从ChangeStart -> OldChangeEnd删除字符串。 已删除的文本 - > OldText.substring(ChangeStart, OldChangeEnd + 1);
ChangeStart > OldChangeEnd 。 在ChangeStart插入字符串。 插入的文本 - > NewText.substring(ChangeStart, NewChangeEnd + 1);
NewText != OldText并且上述两个条件不符合，则它是替代品。 旧字符串中被替换的文本 - > OldText.substring(ChangeStart, OldChangeEnd + 1);
替换文本 - > NewText.substring(ChangeStart, NewChangeEnd + 1);
替换后的OldText中的开始和结束位置ChangeStart -> OldChangeEnd
我已经创建了一个jsfiddle，它包含了我在代码中提到的更改。 你可能想看看它。 希望它能让你从正确的方向开始。
我遇到了类似的问题，并通过以下方式解决了问题：
function diff(oldText, newText) {
// Find the index at which the change began
var s = 0;
while(s < oldText.length && s < newText.length && oldText[s] == newText[s]) {
s++;
}
// Find the index at which the change ended (relative to the end of the string)
var e = 0;
while(e < oldText.length &&
e < newText.length &&
oldText.length - e > s &&
newText.length - e > s &&
oldText[oldText.length - 1 - e] == newText[newText.length - 1 - e]) {
e++;
}
// The change end of the new string (ne) and old string (oe)
var ne = newText.length - e;
var oe = oldText.length - e;
// The number of chars removed and added
var removed = oe - s;
var added = ne - s;
var type;
switch(true) {
case removed == 0 && added > 0: // It's an 'add' if none were removed and at least 1 added
type = 'add';
break;
case removed > 0 && added == 0: // It's a 'remove' if none were added and at least one removed
type = 'remove';
break;
case removed > 0 && added > 0: // It's a replace if there were both added and removed characters
type = 'replace';
break;
default:
type = 'none'; // Otherwise there was no change
s = 0;
}
return { type: type, start: s, removed: removed, added: added };
}
请注意，这并没有解决我的实际问题。 我的问题是我有一个带有段落的编辑器，每个编辑器都用文本建模，并且使用开始和结束索引定义一系列标记，例如从char 1到char 5的粗体。我使用它来检测字符串的更改，以便可以移动相应的标记指数。 但考虑一下字符串：
xx xxxx xx
diff函数方法无法区分在粗体之外或在粗体之内添加的字符。
最后，我采用了一种完全不同的方法 - 我只是解析了编辑器生成的HTML，并使用它来确定标记的开始和结束索引。
制作我自己的稍微更高性能的版本，其灵感来自与上述相同的策略（寻找从前到后和从后到前的差异）
function compareText(oldText, newText)
{
var difStart,difEndOld,difEndNew;
//from left to right - look up the first index where characters are different
for(let i=0;i<oldText.length;i++)
{
if(oldText.charAt(i) !== newText.charAt(i))
{
difStart = i;
break;
}
}
//from right to left - look up the first index where characters are different
//first calc the last indices for both strings
var oldMax = oldText.length - 1;
var newMax = newText.length - 1;
for(let i=0;i<oldText.length;i++)
{
if(oldText.charAt(oldMax-i) !== newText.charAt(newMax-i))
{
//with different string lengths, the index will differ for the old and the new text
difEndOld = oldMax-i;
difEndNew = newMax-i;
break;
}
}
var removed = oldText.substr(difStart,difEndOld-difStart+1);
var added = newText.substr(difStart,difEndNew-difStart+1);
return [difStart,added,removed];
}