我想找出比较两个字符串的更改次数。示例:
字符串1:
我希望借此机会做点好事。我想我的测试表会在ODI中帮助我。在国际板球比赛中得分,无论格式,给球员信心。
字符串2:
"我希望这次能做点好事。我想我的测试表会用ODI格式帮助我。在最新的国际板球比赛中得分,无论格式如何,都会给人一种比赛的信心。"
预期输出:5.(忽略空格和换行符)
更改为:
- from(从字符串2中删除)
- 测试(在字符串2中修改)
- 格式(字符串2中的额外加法)
- 最新(字符串2中的额外添加)
- 演奏(在弦2中修改)
有计算变化次数的算法吗?
您的问题与比较两个文件非常相似。。不同之处在于文件中的比较文件是通过比较单行中的文本来进行比较的。在您的情况下,空白将是一个分隔符,而不是换行符。
通常,这是通过查找最长公共子序列来完成的。以下是一份相关文件,对其进行了解释:https://nanohub.org/infrastructure/rappture/export/2719/trunk/gui/src/diff.pdf
用于查找LCS:
public static int GetLCS(string str1, string str2)
{
int[,] table;
return GetLCSInternal(str1, str2, out table);
}
private static int GetLCSInternal(string str1, string str2, out int[,] matrix)
{
matrix = null;
if (string.IsNullOrEmpty(str1) || string.IsNullOrEmpty(str2))
{
return 0;
}
int[,] table = new int[str1.Length + 1, str2.Length + 1];
for (int i = 0; i < table.GetLength(0); i++)
{
table[i, 0] = 0;
}
for(int j= 0;j<table.GetLength(1); j++)
{
table[0,j] = 0;
}
for (int i = 1; i < table.GetLength(0); i++)
{
for (int j = 1; j < table.GetLength(1); j++)
{
if (str1[i-1] == str2[j-1])
table[i, j] = table[i - 1, j - 1] + 1;
else
{
if (table[i, j - 1] > table[i - 1, j])
table[i, j] = table[i, j - 1];
else
table[i, j] = table[i - 1, j];
}
}
}
matrix = table;
return table[str1.Length, str2.Length];
}
//读出按字典顺序排序的所有LCS
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
namespace LambdaPractice
{
class Program
{
static int[,] c;
static int max(int a, int b)
{
return (a > b) ? a : b;
}
static int LCS(string s1, string s2)
{
for (int i = 1; i <= s1.Length; i++)
c[i,0] = 0;
for (int i = 1; i <= s2.Length; i++)
c[0, i] = 0;
for (int i=1;i<=s1.Length;i++)
for (int j = 1; j <= s2.Length; j++)
{
if (s1[i-1] == s2[j-1])
c[i, j] = c[i - 1, j - 1] + 1;
else
{
c[i, j] = max(c[i - 1, j], c[i, j - 1]);
}
}
return c[s1.Length, s2.Length];
}
/*打印一个LCS静态字符串BackTrack(字符串s1、字符串s2、int i、int j){
if (i == 0 || j == 0)
return "";
if (s1[i - 1] == s2[j - 1])
return BackTrack(s1, s2, i - 1, j - 1) + s1[i - 1];
else if (c[i - 1, j] > c[i, j - 1])
return BackTrack(s1, s2, i - 1, j);
else
return BackTrack(s1, s2, i, j - 1);
}*/
static SortedSet<string> backtrack(string s1, string s2, int i, int j)
{
if (i == 0 || j == 0)
return new SortedSet<string>(){""} ;
else if (s1[i - 1] == s2[j - 1])
{
SortedSet<string> temp = new SortedSet<string>();
SortedSet<string> holder = backtrack(s1, s2, i - 1, j - 1);
if (holder.Count == 0)
{
temp.Add(s1[i - 1]);
}
foreach (string str in holder)
temp.Add(str + s1[i - 1]);
return temp;
}
else
{
SortedSet<string> Result = new SortedSet<string>() ;
if (c[i - 1, j] >= c[i, j - 1])
{
SortedSet<string> holder = backtrack(s1, s2, i - 1, j);
foreach (string s in holder)
Result.Add(s);
}
if (c[i, j - 1] >= c[i - 1, j])
{
SortedSet<string> holder = backtrack(s1, s2, i, j - 1);
foreach (string s in holder)
Result.Add(s);
}
return Result;
}
}
static void Main(string[] args)
{
string s1, s2;
s1 = Console.ReadLine();
s2 = Console.ReadLine();
c = new int[s1.Length+1, s2.Length+1];
LCS(s1, s2);
// Console.WriteLine(BackTrack(s1, s2, s1.Length, s2.Length));
// Console.WriteLine(s1.Length);
SortedSet<string> st = backtrack(s1, s2, s1.Length, s2.Length);
foreach (string str in st)
Console.WriteLine(str);
GC.Collect();
Console.ReadLine();
}
}
}
你能检查一下这是否有用吗?我想说你会对结果集使用很多控制语句(if/else或switch)。
如果您将一个字符串视为modified
(如果它以另一个字符串开头),则可以相对轻松地完成此操作
void Main()
{
var a = "I hope to do something good from this chance.I think my Test form will help me in ODI.Scoring runs in international cricket, regardless of the format, gives a player confidence.";
var b = "I hope to do something good this chance. I think my Testing form will help me in ODI Format. Scoring runs in latest international cricket, regardless of the format, gives a playing confidence.";
var d = new Difference(a,b);
Console.WriteLine("Number of differences: {0}", d.Count);
foreach (var diff in d.Differences)
{
Console.WriteLine("Different: {0}", diff);
}
}
class Difference
{
string a;
string b;
List<string> notInA;
List<string> notInB;
public int Count
{
get { return notInA.Count + notInB.Count; }
}
public IEnumerable<string> Differences
{
get { return notInA.Concat(notInB); }
}
public Difference(string a, string b)
{
this.a = a;
this.b = b;
var itemsA = Split(a);
var itemsB = Split(b);
var changedPairs =
from x in itemsA
from y in itemsB
where (x.StartsWith(y) || y.StartsWith(x)) && y != x
select new { x, y };
var softChanged = changedPairs.SelectMany(p => new[] {p.x, p.y}).Distinct().ToList();
notInA = itemsA.Except(itemsB).Except(softChanged).ToList();
notInB = itemsB.Except(itemsA).Except(softChanged).ToList();
}
IEnumerable<string> Split(string x)
{
return x.Split(new[] { " ", ".", ","}, StringSplitOptions.RemoveEmptyEntries);
}
}
输出:
Number of differences: 5
Different: from
Different: player
Different: Format
Different: latest
Different: playing