查找兩個字符串中存在的最長文本片段

我需要查找兩個字符串中存在的最長文本片段以及兩個字符串片段的起始行數。在這種情況下，我將文本存儲在Book類中，因爲這對我需要處理的其他事情很有意義。我需要一種方法我的主類中，這將是這個樣子：查找兩個字符串中存在的最長文本片段

static void FindLongestFragment(Book book1, Book book2, out string fragment, out int lineNumber1, out int lineNumber2)

不過，我想不出一個算法來做到這一點的。這是我的計劃看起來是什麼至今：

class Book 
{ 
    static char[] Separators = new char[] { ' ', '.', ',', '!', ':', ';', '(', ')', '\t', '\n', '\'', '"', '"' }; 

    public string Text { get; private set; } 
    public LineContainer Lines { get; private set; } 

    public string[] Words { get { return Text.Split(Separators); } } 

    public Book(string[] lines) 
    { 
     Text = ""; 
     for (int i = 0; i < lines.Length; i++) 
     { 
      Text += lines[i] + Environment.NewLine; 
     } 

     Lines = new LineContainer(lines); 
    } 


class LineContainer 
{ 
    private List<Line> Lines; 
    public int Count { get { return Lines.Count; } } 

    public LineContainer(string[] lines) 
    { 
     Lines = new List<Line>(); 
     for (int i = 0; i < lines.Length; i++) 
     { 
      Lines.Add(new Line(lines[i], i)); 
     } 
    } 

    public Line Get(int index) 
    { 
     return Lines[index]; 
    } 
} 

class Line 
{ 
    static char[] Separators = new char[] { ' ', '.', ',', '!', ':', ';', '(', ')', '\t', '\n', '\'', '"', '"' }; 

    public string Text { get; private set; } 
    public int Length { get { return Text.Length; } } 
    public int Number { get; private set; } 

    public string[] Words { get { return Text.Split(Separators); } } 

    public Line(string text, int number) 
    { 
     Text = text; 
     Number = number; 
    } 
}

來源

2016-11-24 PoVa

好像功課......你應該張貼您的預期輸入和輸出爲「最長文本片段」太模糊了。 –

[最長公共子串]（https://en.wikipedia.org/wiki/Longest_common_substring_problem）？甚至有你需要實現的僞代碼... –

@AdrianoRepetti是的，這是我一直在尋找的東西。 – PoVa

嗯，這裏有一些想法...

你可以通過創建2 SortedSet從每個文件中的單詞開始。這樣，你就可以確定哪些單詞只在一個文件中。這樣，你會有每一個包含在另一個字符串中的單詞的序列。

之後，您可能需要構建一個包含給定單詞的所有可能的開始索引的字典：Dictionary<string, List<int>>。

然後，對於第一個字符串的每個開始單詞，您可能希望找到最佳匹配。你會記得找到的最好的比賽。這樣，你可以消除任何太短的序列，而不是那時候最好的序列。

爲此目的，可能會有一個有趣的詞典，它會給出起始詞的最大長度。這樣，你可以很容易地消除很多序列。

另一個可能有助於過濾的技巧是在連續對上構建信息。這樣，也可以在只有一個詞組中存在一對詞的任何點處切斷序列。

所以，如果你在一個循環或遞歸這些步驟，你會很快消除很多情況下...

來源

2016-11-24 21:08:49 Phil1970

查找兩個字符串中存在的最長文本片段

回答

相關問題