Слова, содержащие как минимум 2 общие буквы

Question

Строка называется 2-согласованной, если каждое слово имеет как минимум 2 буквы, общие со следующим словом.

---

Например

"Атом другой эпохи" [atom имеет a а также t общего с another а также another имеет e а также a общего с era (ответ не уникален).

Прежде всего мне нужна структура данных, которая занимает 2 слова и ответы в постоянном времени на вопрос "Do these words have at least 2 letters in common?"

Теперь, учитывая строку n слова мне нужно найти самую длинную 2-согласованную подстроку.

Я не могу понять, какую структуру данных использовать. Я думал radix tree или же prefix tree, но я не смог найти ответ. Вы можете мне помочь?

Answer 1

Принимая буквы без акцента и игнорируя заглавные буквы, для каждого слова вы можете сохранить битовое поле в 32-битном целом числе, где биты 0-25 установлены в 1, если присутствует соответствующая буква из az.

Целое число может быть вычислено за линейное время следующим образом:

int getBitField(char* word)
{
    int bits = 0;
    while(*word)
        bits |= 1 << ((*word++) - 'a');
    return bits;
}

Если предполагается, что слова являются словами на английском или другом языке, с максимальной длиной слова, тогда разница между постоянным и линейным временем является совершенно бессмысленной, поскольку (ради аргумента) все слова, меньшие максимальной длины, могут быть дополнены. с несовпадающими символами, что приведет к алгоритму с постоянным временем.

Когда у вас есть битовые поля для двух слов, вы можете проверить, являются ли они 2-согласованными в постоянное время, сложив их вместе и проверив, если результат не равен нулю (что означает отсутствие общих букв), а не степени 2 (что будет означать только одну общую букву, так как установлен только один бит). Вы можете проверить степень 2, добавив число к себе минус 1.

bool is2Consistent(int word1bits, int word2bits)
{
    int common = word1bits & word2bits;
    return (common & (common - 1)) != 0;
}

Это не сработает, если вы намерены определить такие слова, как "встреча" и "говядина", которые повторяются как 2-согласованные.

Если вы хотите проверить 3-согласованность, вам просто нужно добавить в функцию дополнительную строку:

bool is3Consistent(int word1bits, int word2bits)
{
    int common = word1bits & word2bits;
    common &= (common - 1);
    return (common & (common - 1)) != 0;
}

И если целое число само с собой минус единица, то просто удаляется наименее значимый бит, поэтому вы можете применять его произвольное количество раз для проверки 4-согласованности, 5-согласованности и т. Д.

Answer 2

Часть 1: Есть wordOne а также wordTwo 2-последовательный?

public bool IsWordsTwoConsistent(string first, string second)
{
    int[] letters = Enumerable.Repeat(0, 26).ToArray();
    int countDoubles = 0;

    foreach (char c in first.toLowerCase())
    {
        letters[(int)c - 97]++;
    }

    foreach (char c in second.toLowerCase())
    {
        if (letters[(int)c - 97] > 0)
            countDoubles++;

        if (countDoubles > 1)
            return true;
    }

    return false;
}

Часть 2: Самая длинная 2-последовательная подстрока

public int GetPositionLongestTwoConsistentSubstring(string input)
{
    string[] wordsArray = input.Split(' ');
    int maxLocation = -1, maxLength = 0;
    int candLocation = -1, candLength = 0;  //candiadate

    for (int i = 0 ; i < wordsArray.Length - 1 ; i++)
    {
        if (IsWordsTwoConsistent(wordsArray[i], wordsArray[i+1]))
        {
            candLength++;
            if (candLocation == -1)
                candLength = i;
        }
        else
        {
            if (candLength > maxLength)
            {
                maxLength = candLength;
                maxLocation = candLocation;
            }           
            candLength = 0;
            candLocation = -1;
        }
    }

    if (candLength > maxLength)
    {
        maxLength = candLength;
        maxLocation = candLocation;
    }

    return maxLocation;
}

Answer 3

Прежде всего мне нужна структура данных, которая принимает 2 слова и ответы в постоянном времени на вопрос "У этих слов есть хотя бы 2 общие буквы?"

Легко. Сначала вычислите матрицу смежности для словаря, который вы используете, где "смежный" определяется как "имеющий как минимум две общие буквы". Я не согласен с комментариями, приведенными выше, хранение даже полного словаря английского языка не очень много данных в эти дни. Хранение полной матрицы смежности может занять слишком много места на ваше усмотрение, поэтому используйте средства разреженного массива.

Теперь имейте в виду, что английское слово - это просто число в базе-26 (или в базе-52, если вы настаиваете на различении заглавных букв), поэтому поиск строки и столбца для пары слов - это операция с постоянным временем, и вы есть решение вашего вопроса.

Конечно, это занимает много места и требует значительных предварительных вычислений, но OP спрашивает о структуре данных для ответа на вопрос в постоянном времени.