Cách tìm chuỗi con lớn nhất từ ​​string1 thành string2

Question

Giả sử tôi có hai chuỗi string1và string2.

var string1 = "images of canadian geese goslings";

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

Tôi cần tìm chuỗi con lớn nhất string1phù hợp với string2.

ở đây chuỗi con lớn nhất sẽ được "canadian geese"khớp trong string2.

Làm thế nào tôi có thể tìm thấy nó? Tôi đã cố gắng đột string1nhập char[]và tìm các từ sau đó kết hợp các từ phù hợp nhưng điều đó không đạt mục tiêu của tôi.

Answer 1

Hãy xem đoạn mã sau 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);
}

}   

Các substringsphương thức trả về tất cả các chuỗi con của chuỗi svới độ dài của length(cho yieldcó một cái nhìn tại các tài liệuhttps://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/yield) Chúng tôi bỏ qua các chuỗi con bắt đầu hoặc kết thúc bằng dấu cách, vì chúng tôi không muốn các khoảng trắng làm cho chuỗi con dài hơn thực tế)

Vòng lặp ngoài lặp qua tất cả các giá trị độ dài có thể có cho các chuỗi con, từ dài nhất (tức là string1.Length) đến ngắn nhất (tức là 1). Sau đó, đối với mỗi chuỗi con có độ dài iđược tìm thấy sẽ được kiểm tra, nếu nó cũng là một chuỗi con của string2. Nếu đúng như vậy, chúng ta có thể dừng lại, vì không thể có bất kỳ chuỗi con chung nào nữa, bởi vì chúng tôi đã kiểm tra tất cả các chuỗi con dài hơn trong các lần lặp trước. Nhưng tất nhiên có thể có các chuỗi con phổ biến khác với độ dàii

Answer 2

cách tiếp cận vòng lặp đẳng cấp - kết quả bao gồm dấu cách te sau ngỗng "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

Lưu ý phụ: canadian và Canadiankhông bằng nhau vì vậy bạn phải sử dụng StringComparison.OrdinalIgnoreCasenếu bạn muốn tìm kiếm không phân biệt chữ hoa chữ thường

Answer 3

Tôi sẽ thêm một cái nữa, bằng cách sử dụng span / readonlymemory để bạn có thể tránh phân bổ tất cả các chuỗi mà các câu trả lời hiện tại tạo ra. Lưu ý rằng tôi đã không thực hiện bất kỳ kiểm tra nào cho không gian bắt đầu hoặc không gian kết thúc vì điều đó dường như không phải là yêu cầu cho câu hỏi. Điều này thực hiện tìm kiếm không phân biệt chữ hoa chữ thường, nếu bạn không muốn, bạn có thể làm cho nó hiệu quả hơn bằng cách sử dụng indexof tích hợp sẵn và loại bỏ các so sánh không phân biệt chữ hoa chữ thường.

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