Bagaimana menemukan substring terbesar dari string1 ke string2

Question

Misalkan saya memiliki dua string string1dan string2.

var string1 = "images of canadian geese goslings";

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

Saya perlu menemukan substring terbesar string1yang cocok string2.

di sini substring terbesar "canadian geese"adalah yang cocok dengan string2.

Bagaimana saya bisa menemukannya? Saya mencoba melanggar string1ke dalam char[]dan menemukan kata-kata kemudian digabung kata cocok tetapi yang gagal tujuan saya.

Answer 1

Lihat kode berikut 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);
}

}   

The substringsMetode mengembalikan semua substring dari string sdengan panjang length(untuk yieldmemiliki melihat dokumentasihttps://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/yield) Kami melewatkan substring yang dimulai atau diakhiri dengan spasi, karena kami tidak ingin spasi membuat substring lebih panjang dari yang sebenarnya)

Loop luar melakukan iterasi melalui semua kemungkinan nilai panjang untuk substring, dari yang terpanjang (yaitu string1.Length) ke yang terpendek (yaitu 1). Kemudian untuk setiap substring yang ditemukan panjangnya idicentang, jika itu juga merupakan substring dari string2. Jika demikian, kita bisa berhenti, karena tidak ada lagi substring umum, karena kita memeriksa semua substring yang lebih panjang di iterasi sebelumnya. Tapi tentu saja mungkin ada substring umum lainnya dengan panjangi

Answer 2

pendekatan loop berkelas - hasilnya termasuk ruang te setelah angsa "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

Catatan samping: canadian dan Canadiantidak sama sehingga Anda harus menggunakan StringComparison.OrdinalIgnoreCasejika Anda ingin mencari case insensitive

Answer 3

Saya akan menambahkan satu lagi, menggunakan span / readonlymemory sehingga Anda dapat menghindari mengalokasikan semua string yang dibuat oleh jawaban saat ini. Catatan Saya tidak melakukan pemeriksaan apa pun untuk ruang awal atau ruang akhir karena itu tampaknya bukan persyaratan untuk pertanyaan tersebut. Ini memang melakukan pencarian tidak peka huruf besar / kecil, jika Anda tidak ingin membuatnya lebih efisien dengan menggunakan indeks bawaan dan menghapus perbandingan tidak peka huruf besar / kecil.

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