Como encontrar a maior substring de string1 para string2

Question

Vamos supor que eu tenha duas cordas string1e string2.

var string1 = "images of canadian geese goslings";

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

Preciso encontrar a maior substring string1correspondente em string2.

aqui, a maior substring será aquela "canadian geese"que corresponde em string2.

Como posso encontrar? Tentei quebrar string1em char[]e encontrar as palavras, em seguida, fundiu palavras combinadas, mas que falhou o meu objectivo.

Answer 1

Dê uma olhada no seguinte código 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);
}

}   

O substringsmétodo retorna todas as substrings da string scom o comprimento de length(para yielddar uma olhada na documentaçãohttps://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/yield) Ignoramos substrings que começam ou terminam com um espaço, pois não queremos que os espaços em branco tornem uma substring mais longa do que realmente é)

O loop externo itera por todos os valores de comprimento possíveis para as substrings, do mais longo (isto é string1.Length) ao mais curto (isto é 1). Então, para cada uma das substrings encontradas, o comprimento ié verificado, se também for uma substring de string2. Se for esse o caso, podemos parar, pois não pode haver nenhuma substring comum mais, porque verificamos todas as substrings mais longas em iterações anteriores. Mas é claro que pode haver outras substrings comuns com comprimentoi

Answer 2

abordagem de loop elegante - o resultado inclui o espaço após os gansos "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

Nota lateral: canadian e Canadiannão são iguais, portanto, você deve usar StringComparison.OrdinalIgnoreCasese quiser pesquisar não diferencia maiúsculas de minúsculas

Answer 3

Vou adicionar mais um, usando span / readonlymemory para que você possa evitar a alocação de todas as strings que as respostas atuais criam. Observe que não fiz nenhuma verificação de espaço inicial ou espaço final, pois isso não parece ser um requisito para a pergunta. Isso faz uma pesquisa sem distinção entre maiúsculas e minúsculas; se você não quiser, pode torná-la mais eficiente usando o indexof integrado e eliminando as comparações sem distinção entre maiúsculas e minúsculas.

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