計數比較兩個字符串在c中的變化次數＃

Question

我想找出比較兩個字符串的變化次數。 例子：

串1：

我希望做一些事情，從這個好再來一次的機會覺得我的測試形式將 幫助我在ODI。無論 的格式如何，得分在國際板球運行，給球員信心。

串2：

「我希望做一件好事這個機會，我想我的測試表格將 幫助我在ODI格式得分運行在最新的國際板球， 無論何種格式。 ，給了打球的信心。「

預期輸出：5（忽略空間&換行符）

的變化是：

1. 從（刪除字符串2），
2. 測試（在串2改性的），
3. 格式（在字符串2中額外添加），
4. 最新（字符串2中額外添加），
5. 正在播放（在字符串2中修改）。

有沒有算法來計算更改的次數？

Answer 1

您的問題與比較兩個文件非常相似..區別在於文件比較文件通過比較單行文本進行比較。在你的情況下，它的空白將是一個分隔符而不是Newline。

通常這是通過找到最長的公共子序列來完成的。這裏有一個相關的文件，其中解釋了它：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（string s1，string 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(); 
    } 
} 
} 

Answer 2

你可以檢查這個might be useful somehow，我會說你會爲結果集使用大量的控制語句（if/else或switch）。

Answer 3

你可以這樣做比較容易，如果你認爲一個字符串作爲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