Найдите длину самого маленького окна, содержащего все символы строки в другой строке

Ответ 1

Я попытался написать некоторый простой c-код для решения проблемы:

Update:

Я написал функцию search, которая ищет нужные символы в правильном порядке, возвращая длину окна и сохраняя начальную точку окна до ìnt * startAt. Функция обрабатывает подпоследовательность заданного сена с указанной начальной точки int start до конца

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

Сложность - O (n * n/2)

Update2:

ненужные зависимости удалены, ненужные последующие вызовы strlen(...) были заменены параметрами размера, переданными в search(...)

#include <stdio.h>

// search for single occurrence
int search(const char hay[], int haySize, const char needle[], int needleSize, int start, int * startAt)
{
    int i, charFound = 0;

    // search from start to end
    for (i = start; i < haySize; i++)
    {
        // found a character ?
        if (hay[i] == needle[charFound])
        {               
            // is it the first one?
            if (charFound == 0) 
                *startAt = i;   // store starting position
            charFound++;    // and go to next one
        }
        // are we done?
        if (charFound == needleSize)
            return i - *startAt + 1;    // success
    }
    return -1;  // failure
}

int main(int argc, char **argv)
{

    char hay[] = "ADCBDABCDACD";
    char needle[] = "ACD";

    int resultStartAt, resultLength = -1, i, haySize = sizeof(hay) - 1, needleSize = sizeof(needle) - 1;

    // search all possible occurrences
    for (i = 0; i < haySize - needleSize; i++)
    {
        int startAt, length;

        length = search(hay, haySize, needle, needleSize, i, &startAt);

        // found something?
        if (length != -1)
        {
            // check if it the first result, or a one better than before
            if ((resultLength == -1) || (resultLength > length))
            {
                resultLength = length;
                resultStartAt = startAt;
            }
            // skip unnecessary steps in the next turn
            i = startAt;
        }
    }

    printf("start at: %d, length: %d\n", resultStartAt, resultLength);

    return 0;
}

Ответ 2

Начните с начала строки.

Если вы столкнулись с A, отметьте позицию и нажмите ее в стеке. После этого продолжайте проверять символы последовательно, пока 1. Если вы столкнулись с A, обновите позицию A до текущего значения.
2. Если вы столкнулись с C, вставьте его в стек.

После того, как вы встретите C, снова продолжайте проверять символы последовательно, пока,
1. Если вы столкнулись с D, сотрите стек, содержащий A и C, и отметьте оценку от A до D для этой подпоследовательности.
2. Если вы столкнулись с A, тогда запустите еще один Stack и отметьте это положение.  2а. Если теперь вы сталкиваетесь с C, удалите предыдущие стеки и сохраните последний стек.
 2b. Если вы столкнулись с D, то удалите старый стек и отметьте счет и проверьте, меньше ли он текущего наилучшего.

Продолжайте делать это, пока не достигнете конца строки.

Псевдокод может выглядеть примерно так:

Initialize stack = empty;
Initialize bestLength = mainString.size() + 1; // a large value for the subsequence.
Initialize currentLength = 0;
for ( int i = 0; i < mainString.size(); i++ ) {

  if ( stack is empty ) {
    if ( mainString[i] == 'A' ) {
      start a new stack and push A on it.
      mark the startPosition for this stack as i.
    }
    continue;
  }

  For each of the stacks ( there can be at most two stacks prevailing, 
                           one of size 1 and other of size 0 ) {
    if ( stack size == 1 ) // only A in it {
      if ( mainString[i] == 'A' ) {
        update the startPosition for this stack as i.
      }
      if ( mainString[i] == 'C' ) {
        push C on to this stack.
      }
    } else if ( stack size == 2 ) // A & C in it {
      if ( mainString[i] == 'C' ) {
        if there is a stack with size 1, then delete this stack;// the other one dominates this stack.
      }
      if ( mainString[i] == 'D' ) {
        mark the score from startPosition till i and update bestLength accordingly.
        delete this stack.
      }
    }

  }

}

Ответ 3

Я изменил свое предыдущее предложение, используя одну очередь, теперь я считаю, что этот алгоритм работает с O(N*m) time:

FindSequence(char[] sequenceList)
{
    queue startSeqQueue;
    int i = 0, k;
    int minSequenceLength = sequenceList.length + 1;
    int startIdx = -1, endIdx = -1;

    for (i = 0; i < sequenceList.length - 2; i++)
    {
        if (sequenceList[i] == 'A')
        {
            startSeqQueue.queue(i);
        }
    }

    while (startSeqQueue!=null)
    {
        i = startSeqQueue.enqueue();
        k = i + 1;

        while (sequenceList.length < k && sequenceList[k] != 'C')
            if (sequenceList[i] == 'A') i = startSeqQueue.enqueue();
            k++;

        while (sequenceList.length < k && sequenceList[k] != 'D')
            k++;

        if (k < sequenceList.length && k > minSequenceLength > k - i + 1)
        {
            startIdx = i;
            endIdx = j;
            minSequenceLength = k - i + 1;
        }
    }

    return startIdx & endIdx
}

Моя предыдущая (O (1) память):

FindSequence(char[] sequenceList)
{
    int i = 0, k;
    int minSequenceLength = sequenceList.length + 1;
    int startIdx = -1, endIdx = -1;

    for (i = 0; i < sequenceList.length - 2; i++)
        if (sequenceList[i] == 'A')
            k = i+1;
            while (sequenceList.length < k && sequenceList[k] != 'C')
                k++;
            while (sequenceList.length < k && sequenceList[k] != 'D')
                k++;

            if (k < sequenceList.length && k > minSequenceLength > k - i + 1)
            {
                startIdx = i;
                endIdx = j;
                minSequenceLength = k - i + 1;
            }

    return startIdx & endIdx;
}

Ответ 4

Вот моя версия. Он отслеживает возможных кандидатов для оптимального решения. Для каждого символа в сене он проверяет, находится ли этот символ в последовательности каждого кандидата. Затем он выбирает самый короткий кандидат. Совсем просто.

class ShortestSequenceFinder
{
    public class Solution
    {
        public int StartIndex;
        public int Length;
    }

    private class Candidate
    {
        public int StartIndex;
        public int SearchIndex;
    }

    public Solution Execute(string hay, string needle)
    {
        var candidates = new List<Candidate>();
        var result = new Solution() { Length = hay.Length + 1 };
        for (int i = 0; i < hay.Length; i++)
        {
            char c = hay[i];
            for (int j = candidates.Count - 1; j >= 0; j--)
            {
                if (c == needle[candidates[j].SearchIndex])
                {
                    if (candidates[j].SearchIndex == needle.Length - 1)
                    {
                        int candidateLength = i - candidates[j].StartIndex;
                        if (candidateLength < result.Length)
                        {
                            result.Length = candidateLength;
                            result.StartIndex = candidates[j].StartIndex;
                        }
                        candidates.RemoveAt(j);
                    }
                    else
                    {
                        candidates[j].SearchIndex += 1;
                    }
                }
            }
            if (c == needle[0])
                candidates.Add(new Candidate { SearchIndex = 1, StartIndex = i });
        }
        return result;
    }
}

Он работает в O (n * m).

Ответ 5

Вот мое решение в Python. Он возвращает индексы, предполагающие 0-индексированные последовательности. Поэтому для данного примера он возвращает (9, 11) вместо (10, 12). Очевидно, что это легко мутировать, чтобы вернуть (10, 12), если хотите.

def solution(s, ss):
    S, E = [], []
    for i in xrange(len(s)):
        if s[i] == ss[0]:
            S.append(i)
        if s[i] == ss[-1]:
            E.append(i)
    candidates = sorted([(start, end) for start in S for end in E
                        if start <= end and end - start >= len(ss) - 1],
                        lambda x,y: (x[1] - x[0]) - (y[1] - y[0]))
    for cand in candidates:
        i, j = cand[0], 0
        while i <= cand[-1]:
            if s[i] == ss[j]:
                j += 1
            i += 1
        if j == len(ss):
            return cand

Использование:

>>> from so import solution
>>> s = 'ADCBDABCDACD'
>>> solution(s, 'ACD')
(9, 11)
>>> solution(s, 'ADC')
(0, 2)
>>> solution(s, 'DCCD')
(1, 8)
>>> solution(s, s)
(0, 11)
>>> s = 'ABC'
>>> solution(s, 'B')
(1, 1)
>>> print solution(s, 'gibberish')
None

Я считаю, что временная сложность O (p log (p)), где p - количество пар индексов в последовательности, которая относится к search_sequence[0] и search_sequence[-1], где индекс для search_sequence[0] меньше, чем index для search_sequence[-1], потому что он сортирует эти p-пары, используя алгоритм O (n log n). Но опять же, моя подстрочная итерация в конце может полностью затмить этот шаг сортировки. Я не уверен.

Вероятно, она имеет худшую временную сложность, которая ограничена O (n * m), где n - длина последовательности, а m - длина последовательности поиска, но на данный момент я не могу придумать пример в худшем случае.

Ответ 6

Вот мой алгоритм O (m * n) в Java:

class ShortestWindowAlgorithm {

    Multimap<Character, Integer> charToNeedleIdx; // Character -> indexes in needle, from rightmost to leftmost | Multimap is a class from Guava
    int[] prefixesIdx; // prefixesIdx[i] -- rightmost index in the hay window that contains the shortest found prefix of needle[0..i]
    int[] prefixesLengths; // prefixesLengths[i] -- shortest window containing needle[0..i]

    public int shortestWindow(String hay, String needle) {
        init(needle);
        for (int i = 0; i < hay.length(); i++) {
            for (int needleIdx : charToNeedleIdx.get(hay.charAt(i))) {
                if (firstTimeAchievedPrefix(needleIdx) || foundShorterPrefix(needleIdx, i)) {
                    prefixesIdx[needleIdx] = i;
                    prefixesLengths[needleIdx] = getPrefixNewLength(needleIdx, i);
                    forgetOldPrefixes(needleIdx);
                }
            }
        }
        return prefixesLengths[prefixesLengths.length - 1];
    }

    private void init(String needle) {
        charToNeedleIdx = ArrayListMultimap.create();
        prefixesIdx = new int[needle.length()];
        prefixesLengths = new int[needle.length()];
        for (int i = needle.length() - 1; i >= 0; i--) {
            charToNeedleIdx.put(needle.charAt(i), i);
            prefixesIdx[i] = -1;
            prefixesLengths[i] = -1;
        }
    }

    private boolean firstTimeAchievedPrefix(int needleIdx) {
        int shortestPrefixSoFar = prefixesLengths[needleIdx];
        return shortestPrefixSoFar == -1 && (needleIdx == 0 || prefixesLengths[needleIdx - 1] != -1);
    }

    private boolean foundShorterPrefix(int needleIdx, int hayIdx) {
        int shortestPrefixSoFar = prefixesLengths[needleIdx];
        int newLength = getPrefixNewLength(needleIdx, hayIdx);
        return newLength <= shortestPrefixSoFar;
    }

    private int getPrefixNewLength(int needleIdx, int hayIdx) {
        return needleIdx == 0 ? 1 : (prefixesLengths[needleIdx - 1] + (hayIdx - prefixesIdx[needleIdx - 1]));
    }

    private void forgetOldPrefixes(int needleIdx) {
        if (needleIdx > 0) {
            prefixesLengths[needleIdx - 1] = -1;
            prefixesIdx[needleIdx - 1] = -1;
        }
    }
}

Он работает на каждом входе, а также может обрабатывать повторяющиеся символы и т.д.

Вот несколько примеров:

public class StackOverflow {

    public static void main(String[] args) {
        ShortestWindowAlgorithm algorithm = new ShortestWindowAlgorithm();
        System.out.println(algorithm.shortestWindow("AXCXXCAXCXAXCXCXAXAXCXCXDXDXDXAXCXDXAXAXCD", "AACD")); // 6
        System.out.println(algorithm.shortestWindow("ADCBDABCDACD", "ACD")); // 3
        System.out.println(algorithm.shortestWindow("ADCBDABCD", "ACD")); // 4
    }

Ответ 7

Я не читал каждый ответ здесь, но я не думаю, что кто-то заметил, что это всего лишь ограниченная версия локального парного выравнивания последовательностей, в котором нам разрешено вставлять только символы (а не удалять или заменять их). Как таковой он будет решен путем упрощения алгоритма Smith-Waterman, который учитывает только 2 случая на вершину (прибытие в вершину либо путем сопоставления характер, или вставка символа), а не 3 случая. Этот алгоритм O (n ^ 2).

Ответ 8

Вот мое решение. Он следует за одним из решений совпадения шаблонов. Пожалуйста, прокомментируйте/исправьте меня, если я ошибаюсь.

Учитывая входную строку как в вопросе A D C B D A B C D A C D. Пусть сначала вычисляются индексы, где A. Предполагая индекс на основе нуля, это должно быть [0,5,9].

Теперь псевдокод выглядит следующим образом.

    Store the indices of A in a list say *orders*.// orders=[0,5,9]
    globalminStart, globalminEnd=0,localMinStart=0,localMinEnd=0;
    for (index: orders)
     {
       int i =index;
       Stack chars=new Stack();// to store the characters
      i=localminStart;
     while(i< length of input string)
       { 
           if(str.charAt(i)=='C') // we've already seen A, so we look for C
           st.push(str.charAt(i));
           i++;
           continue;
           else if(str.charAt(i)=='D' and st.peek()=='C')
           localminEnd=i; // we have a match! so assign value of i to len
           i+=1;
           break;
           else if(str.charAt(i)=='A' )// seen the next A
           break;
    }
     if (globalMinEnd-globalMinStart<localMinEnd-localMinStart)
     {
       globalMinEnd=localMinEnd;
       globalMinStart=localMinStart;
     }
   }

    return [globalMinstart,globalMinEnd]
    }

P.S: это псевдокод и приблизительная идея. Id будет рад исправить это и понять, если что-то не так.

AFAIC Сложность времени -O (n). Космическая сложность O (n)