So finden Sie den größten Teilstring von string1 in string2

Question

Nehmen wir an, ich habe zwei Saiten string1und string2.

var string1 = "images of canadian geese goslings";

var string2 = "Canadian geese with goslings pictures to choose from, with no signup needed";

Ich muss den größten Teilstring finden, der dazu string1passt string2.

Hier wird der größte Teilstring sein, "canadian geese"der dazu passt string2.

Wie kann ich es finden? Ich habe versucht, string1in char[]Wörter einzubrechen und sie zu finden, dann habe ich übereinstimmende Wörter zusammengeführt, aber das hat mein Ziel verfehlt.

Answer 1

Schauen Sie sich den folgenden Code an https://dotnetfiddle.net/aPyw3o

public class Program {

static IEnumerable<string> substrings(string s, int length) {
    for (int i = 0 ; i + length <= s.Length; i++) {
        var ss = s.Substring(i, length);
        if (!(ss.StartsWith(" ") || ss.EndsWith(" ")))
            yield return ss;
    }
}

public static void Main()
{
    int count = 0;
    var string1 = "images of canadian geese goslings";
    var string2 = "Canadian geese with goslings pictures to choose from, with no signup needed";
    string result = null;
    for (int i = string1.Length; i>0 && string.IsNullOrEmpty(result); i--) {
        foreach (string s in substrings(string1, i)) {
            count++;
            if (string2.IndexOf(s, StringComparison.CurrentCultureIgnoreCase) >= 0) {
                result = s;
                break;
            }
        }
    }
    if (string.IsNullOrEmpty(result)) 
        Console.WriteLine("no common substrings found");
    else 
        Console.WriteLine("'" + result + "'");
    Console.WriteLine(count);
}

}   

Die substringsMethode gibt alle Teilzeichenfolgen des Strings smit der Länge von zurück length( yieldsiehe Dokumentation)https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/yield) Wir überspringen Teilzeichenfolgen, die mit einem Leerzeichen beginnen oder enden, da wir nicht möchten, dass Leerzeichen eine Teilzeichenfolge länger machen als sie wirklich ist.)

Die äußere Schleife durchläuft alle möglichen Längenwerte für die Teilzeichenfolgen, vom längsten (dh string1.Length) bis zum kürzesten (dh 1). Dann wird für jede der gefundenen Teilzeichenfolgen der Länge igeprüft, ob es sich auch um eine Teilzeichenfolge von handelt string2. Wenn dies der Fall ist, können wir aufhören, da es keine gemeinsame Teilzeichenfolge mehr geben kann, da wir in früheren Iterationen alle längeren Teilzeichenfolgen überprüft haben. Aber natürlich kann es auch andere gängige Teilzeichenfolgen mit Länge gebeni

Answer 2

Classy-Loop-Ansatz - das Ergebnis ist der Platz nach Gänsen "canadian geese "

var string1 = "images of canadian geese goslings";
var string2 = "Canadian geese with goslings pictures to choose from, with no signup needed";

string result = "";

for (int i = 0; i < string1.Length; i++)
{
    for (int j = 0; j < string1.Length - i; j++)
    {
        //add .Trim() here if you want to ignore space characters
        string searchpattern = string1.Substring(i, j);
        if (string2.IndexOf(searchpattern,  StringComparison.OrdinalIgnoreCase) > -1 && searchpattern.Length > result.Length)
        {
            result = searchpattern;
        }
    }
}

https://dotnetfiddle.net/q3rHjI

Randnotiz: canadian und Canadiansind nicht gleich, so dass Sie verwenden müssen, StringComparison.OrdinalIgnoreCasewenn Sie die Groß- und Kleinschreibung nicht berücksichtigen möchten

Answer 3

Ich werde noch eine hinzufügen, indem ich span / readonlymemory verwende, damit Sie vermeiden können, alle Zeichenfolgen zuzuweisen, die die aktuellen Antworten erstellen. Hinweis: Ich habe keine Überprüfung des Start- oder Endbereichs durchgeführt, da dies keine Voraussetzung für die Frage zu sein scheint. Dies führt eine Suche ohne Berücksichtigung der Groß- und Kleinschreibung durch. Wenn Sie nicht möchten, dass die Suche effizienter wird, indem Sie den integrierten Index von verwenden und die Vergleiche ohne Berücksichtigung der Groß- und Kleinschreibung löschen.

    static void Main(string[] _)
    {
        var string1 = "images of canadian geese goslings";

        var string2 = "Canadian geese with goslings pictures to choose from, with no signup needed";

        var longest = FindLongestMatchingSubstring(string1, string2);

        Console.WriteLine(longest);
    }

    static string FindLongestMatchingSubstring(string lhs, string rhs)
    {
        var left = lhs.AsMemory();
        var right = rhs.AsMemory();

        ReadOnlyMemory<char> longest = ReadOnlyMemory<char>.Empty;

        for (int i = 0; i < left.Length; ++i)
        {
            foreach (var block in FindMatchingSubSpans(left, i, right))
            {
                if (block.Length > longest.Length)
                    longest = block;
            }
        }

        if (longest.IsEmpty)
            return string.Empty;

        return longest.ToString();
    }

    static IEnumerable<ReadOnlyMemory<char>> FindMatchingSubSpans(ReadOnlyMemory<char> source, int pos, ReadOnlyMemory<char> matchFrom)
    {
        int lastMatch = 0;

        for (int i = pos; i < source.Length; ++i)
        {
            var ch = source.Span[i];

            int match = IndexOfChar(matchFrom, lastMatch, ch);

            if (-1 != match)
            {
                lastMatch = match + 1;

                int end = i;

                while (++end < source.Length && ++match < matchFrom.Length)
                {
                    char lhs = source.Span[end];
                    char rhs = matchFrom.Span[match];

                    if (lhs != rhs && lhs != (char.IsUpper(rhs) ? char.ToLower(rhs) : char.ToUpper(rhs)))
                    {
                        break;
                    }
                }

                yield return source.Slice(i, end - i);
            }
        }
    }

    static int IndexOfChar(ReadOnlyMemory<char> source, int pos, char ch)
    {
        char alt = char.IsUpper(ch) ? char.ToLower(ch) : char.ToUpper(ch);

        for (int i = pos; i < source.Length; ++i)
        {
            char m = source.Span[i];

            if (m == ch || m == alt)
                return i;
        }

        return -1;
    }