String1'den string2'ye en büyük alt dizeyi bulma

Question

Diyelim ki iki dizim var string1ve string2.

var string1 = "images of canadian geese goslings";

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

İçinde string1eşleşen en büyük alt dizeyi bulmam gerekiyor string2.

burada "canadian geese"eşleşen en büyük alt dize olacaktır string2.

Nasıl bulabilirim? İçeri string1girmeyi char[]ve kelimeleri bulmayı denedim, sonra eşleşen kelimeleri birleştirdim ama bu amacım başarısız oldu.

Answer 1

Aşağıdaki koda bir göz atın 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);
}

}   

substringsYöntem dizesinin tüm alt dizeleri döndürür suzunluğu ile lengthiçin ( yieldbelgelerine bir gözhttps://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/yield) Beyaz boşlukların bir alt dizeyi gerçekte olduğundan daha uzun yapmasını istemediğimiz için boşlukla başlayan veya biten alt dizeleri atlarız)

Dış döngü, en uzundan (yani string1.Length) en kısaya (yani 1) alt dizeler için olası tüm uzunluk değerlerini yineler . Ardından, bulunan her alt dizge için, iaynı zamanda bir alt dizesi ise kontrol edilir string2. Durum buysa, artık ortak bir alt dize olamayacağından durabiliriz, çünkü önceki yinelemelerde tüm uzun alt dizeleri kontrol ettik. Ancak elbette, uzunluğu olan başka yaygın alt dizeler de olabilir.i

Answer 2

klas döngü yaklaşımı - sonuç kazlardan sonraki boşluğu içerir "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

Yan not: canadian ve Canadianeşit değildir, bu nedenle StringComparison.OrdinalIgnoreCasebüyük / küçük harfe duyarlı olmayan arama yapmak istiyorsanız kullanmanız gerekir

Answer 3

Span / readonlymemory kullanarak bir tane daha ekleyeceğim, böylece mevcut cevapların oluşturduğu tüm dizeleri ayırmaktan kurtulabilirsiniz. Not Başlangıç ​​boşluğu veya bitiş boşluğu için herhangi bir kontrol yapmadım, çünkü bu soru için bir gereklilik gibi görünmüyor. Bu, büyük / küçük harfe duyarlı olmayan bir arama yapar, eğer yerleşik indexof kullanarak ve büyük / küçük harfe duyarlı olmayan karşılaştırmaları kaldırarak daha verimli hale getirebilmenizi istemiyorsanız.

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