Suche nach dem längsten Textfragment, das in beiden Strings existiert

Question

Ich muss das längste Textfragment finden, das in beiden Zeichenfolgen vorhanden ist und die Nummer der Zeile, in der das Fragment für beide Zeichenfolgen beginnt. In diesem Fall speichere ich den Text in Book Klasse, weil es für andere Dinge Sinn macht, die ich damit zu tun habe. Ich brauche eine Methode in meinem Hauptklasse, die wie folgt aussehen würde:

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

Allerdings habe ich nicht von einem Algorithmus, dies zu tun denken kann. Hier ist, was mein Programm sieht so weit:

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; 
    } 
} 

Answer 1

Nun, hier sind einige Ideen ...

Sie beginnen könnte von 2 SortedSet Erstellung mit den Worten aus jeder Datei. Auf diese Weise können Sie bestimmen, welche Wörter nur in einer Datei enthalten sind. Auf diese Weise enthält jede Sequenz Wörter, die sich in der anderen Zeichenfolge befinden.

Danach sollten Sie ein Wörterbuch erstellen, das alle möglichen Startindizes für ein gegebenes Wort enthält: Dictionary<string, List<int>>.

Dann möchten Sie vielleicht für jedes Anfangswort der ersten Zeichenfolge die bestmögliche Übereinstimmung finden. Sie würden sich an das beste gefundene Spiel erinnern. Auf diese Weise können Sie jede Sequenz eliminieren, die zu kurz ist, um an dieser Stelle die beste zu sein.

Für diesen Zweck könnte es interessant sein, ein Wörterbuch zu haben, das die maximale Länge von einem Anfangswort geben würde. Auf diese Weise können Sie viele Sequenzen besonders leicht eliminieren.

Ein weiterer Trick, der beim Filtern helfen könnte, wäre das Erstellen von Informationen über aufeinanderfolgende Paare. Auf diese Weise wäre es auch möglich, die Sequenz an jedem Punkt zu unterbrechen, an dem ein Wortpaar nur in einer Phrase existiert.

Also, wenn Sie diese Schritte in einer Schleife oder rekursiv tun, würden Sie schnell eine Menge von Fällen beseitigen ...