Как определить строку S можно сделать из строки T, удалив некоторые символы, но не более K последовательных символов

Ответ 1

(Обновление: я переписал открытие этого ответа, чтобы включить обсуждение сложности и обсудить некоторые альтернативные методы и потенциальные риски.)

(Короткий ответ, единственное реальное улучшение выше подхода O (nm), о котором я могу думать, - это наблюдать, что нам обычно не нужно вычислять все n раз m записей в таблице. Мы можем вычислить только те ячейки нам нужно, но на практике это может быть очень хорошо, в зависимости от набора данных.)

Уточнить проблему: у нас есть строка S длины n и строка T длины m. Максимально допустимый зазор составляет k - этот зазор должен применяться и в начале и в конце строки. Разрыв - это количество непревзойденных символов между двумя совпадающими символами - т.е. Если буквы смежны, это пробел 0, а не 1.

Представьте таблицу с n+1 строками и столбцами m+1.

      0  1  2  3  4  ... m
     --------------------
0   | ?  ?  ?  ?  ?      ?
1   | ?  ?  ?  ?  ?      ?
2   | ?  ?  ?  ?  ?      ?
3   | ?  ?  ?  ?  ?      ?
... |
n   | ?  ?  ?  ?  ?      ?

Сначала мы могли бы определить, что запись в строке r и столбце c является двоичным флагом, который сообщает нам, являются ли первые r символы S допустимой k -последовательностью из первых c символов T. (Не волнуйтесь, как вычислить эти значения, или даже если эти значения полезны, нам просто нужно определить их в первую очередь.)

Однако эта таблица двоичного флага не очень полезна. Невозможно легко вычислить одну ячейку как функцию близлежащих клеток. Вместо этого нам нужно, чтобы каждая ячейка хранила немного больше информации. Также, как и запись того, соответствуют ли соответствующие строки правильной подпоследовательности, нам нужно записать количество последовательных непревзойденных символов в конце нашей подстроки T (подстрока с символами c). Например, если первые r=2 символы S являются "ab", а первые c=3 символы T являются "abb", тогда возможны два возможных совпадения: первые символы, очевидно, совпадают друг с другом, но b может совпадать с любым из последних b. Поэтому у нас есть выбор оставить один или ноль непревзойденного b в конце. Какой из них мы записываем в таблице?

Ответ заключается в том, что если ячейка имеет несколько допустимых значений, то мы берем наименьшую из них. Логично, что мы хотим сделать жизнь максимально легкой для себя, сопоставляя остальную часть строки, и, следовательно, чем меньше разрыв в конце, тем лучше. Будьте осторожны с другими неправильными выборами - мы не хотим сопоставлять столько символов, сколько возможно, или как несколько символов. Это может иметь неприятные последствия. Но для данной пары строк S,T логично найти совпадение (если есть какие-либо допустимые соответствия), который минимизирует разрыв в конце.

Еще одно замечание состоит в том, что если строка S намного короче T, то она не может совпадать. Это также зависит от k. Максимальная длина, которую может покрывать S, составляет rk, если она меньше c, тогда мы можем легко пометить (r,c) как -1.

(Любые другие утверждения оптимизации, которые могут быть сделаны?)

Нам не нужно вычислять все значения в этой таблице. Число различных возможных состояний k + 3. Они начинаются в состоянии undefined '(?). Если совпадение невозможно для пары (под) строк, состояние -. Если совпадение возможно, то оценка в ячейке будет числом от 0 до k включительно, записывая наименьшее возможное количество непревзойденных последовательных символов в конце. Это дает нам общее число k + 3.

Нам интересна только запись в правом нижнем углу таблицы. Если f(r,c) - это функция, которая вычисляет конкретную ячейку, то нас интересует только f(n,m). Значение для конкретной ячейки может быть вычислено как функция близких значений. Мы можем построить рекурсивный алгоритм, который принимает в качестве входных данных r и c и выполняет соответствующие вычисления и поиски в терминах близких значений. Если эта функция просматривает f(r,c) и находит ?, она будет продолжать и вычислять ее, а затем сохранять ответ.

Важно сохранить ответ, поскольку алгоритм может запрашивать одну и ту же ячейку много раз. Но также, некоторые клетки никогда не будут вычислены. Мы просто начинаем пытаться вычислить одну ячейку (внизу справа) и просто искать и вычислять и хранить по мере необходимости.

Это "очевидный" подход O (nm). Единственная оптимизация здесь - это наблюдение, что нам не нужно вычислять все ячейки, поэтому это должно привести к сложности ниже O (nm). Конечно, с действительно неприятными наборами данных, вы можете в конечном итоге вычислить почти все ячейки! Поэтому сложно поставить официальную оценку сложности.

Наконец, я должен сказать, как вычислить определенную ячейку f(r,c):

• Если r==0 и c <= k, тогда f(r,c) = 0. Пустая строка может соответствовать любой строке с символами k.
• Если r==0 и c > k, тогда f(r,c) = -1. Слишком долго для матча.
• Есть только два других способа, которыми ячейка может иметь успешное состояние. Сначала мы попробуем:
• • Если S[r]==T[c] и f(r-1,c-1) != -1, тогда f(r,c) = 0. Это лучший случай - матч без отставания.
• • Если это не сработало, мы попробуем следующее лучшее. Если f(r,c-1) != -1 и f(r,c) < k, тогда f(r,c) = f(r,c-1)+1.
• • Если ни один из них не работает, тогда f(r,c) = -1.

Остальная часть этого ответа - мой первоначальный подход на основе Haskell. Одно из преимуществ этого заключается в том, что он "понимает", что ему не нужно вычислять каждую ячейку, а только вычислить ячейки там, где это необходимо. Но это может привести к неэффективности вычисления одной ячейки много раз.

* Также обратите внимание, что подход Haskell эффективно подходит к проблеме в зеркальном изображении - он пытается построить совпадения от концевых подстрок S и T, где минимальная ведущая пучка непревзойденных символов. У меня нет времени переписать его в форме "зеркального изображения"!

Рекурсивный подход должен работать. Нам нужна функция, которая будет принимать три аргумента: int k, String S и String T. Однако нам не просто нужен логический ответ о том, является ли S действительной k-подпоследовательностью T.

Для этого рекурсивного подхода, если S - действительная k-подпоследовательность, мы также хотим знать о лучшей возможной подпоследовательности, возвращая, как можно отбросить несколько символов с начала T. Мы хотим найти "лучшую" подпоследовательность. Если k-подпоследовательность невозможна для S и T, то мы возвращаем -1, но если это возможно, мы хотим вернуть наименьшее количество символов, которые мы можем вытащить из T, сохраняя свойство k-подпоследовательности.

    helloworld
      l    r d

Это действительная 4-подпоследовательность, но наибольший разрыв имеет (самое большее) четыре символа (lowo). Это лучшая подпоследовательность, потому что она оставляет пробел всего двух символов в начале (he). В качестве альтернативы, здесь есть еще одна действительная k-подпоследовательность с теми же строками, но она не так хороша, потому что она оставляет зазор в три раза:

    helloworld
       l   r d

Это написано в Haskell, но должно быть достаточно легко переписать на любой другой язык. Я разберу его более подробно ниже.

best :: Int -> String -> String -> Int
--      K      S         T         return
--          where len(S) <= len(T)

best    k      []        t_string       -- empty S is a subsequence of anything!
        | length(t_string) <= k       = length(t_string)
        | length(t_string) >  k       = -1

best    k      [email protected](s:ss) []       = (-1)  -- if T is empty, and S is non-empty, then no subsequence is possible
best    k      [email protected](s:ss) [email protected](t:ts)       -- both are non-empty.  Various possibilities:
        | s == t  &&   best k ss  ts /= -1     =  0    --  if  s==t, and if    best k ss ts != -1, then we have the best outcome
        | best k sss ts /= -1 
                  &&   best k sss ts < k       = 1+ (best k sss ts)  -- this is the only other possibility for a valid k-subsequence
        | otherwise                            = -1     -- no more options left, return -1 for failure.

Поэтапный анализ: (Комментарий в Haskell начинается с --)

best :: Int -> String -> String -> Int

Функция, которая принимает Int и две строки и возвращает Int. Возвращаемое значение должно быть -1, если k-подпоследовательность невозможна. В противном случае он вернет целое число от 0 до K (включительно), сообщив нам наименьший возможный пробел в начале T.

Мы просто разбираем дела по порядку.

best    k      []        t       -- empty S is a subsequence of anything!
        | length(t) <= k       = length(t)
        | length(t) >  k       = -1

Выше мы обрабатываем случай, когда S пусто ([]). Это просто, так как пустая строка всегда является допустимой подпоследовательностью. Но чтобы проверить, является ли это допустимой k-подпоследовательностью, мы должны вычислить длину T.

best    k      [email protected](s:ss) []       = (-1)
   -- if T is empty, and S is non-empty, then no subsequence is possible

Этот комментарий объясняет это. Это оставляет нас в ситуациях, когда обе строки непусты:

best    k      [email protected](s:ss) [email protected](t:ts)       -- both are non-empty.  Various possibilities:
        | s == t  &&   best k ss  ts /= -1     =  0    --  if  s==t, and if    best k ss ts != -1, then we have the best outcome
        | best k sss ts /= -1 
                  &&   best k sss ts < k       = 1+ (best k sss ts)  -- this is the only other possibility for a valid k-subsequence
        | otherwise                            = -1     -- no more options left, return -1 for failure.

[email protected](t:ts) соответствует непустой строке. Имя строки tts. Но в Haskell есть также удобный трюк, позволяющий вам давать имена первой букве в строке (T) и остаток строки (ts). Здесь ts следует читать вслух, поскольку множественное число T - суффикс S здесь означает "множественное число". Мы говорим, что имеем T и некоторые ts, и вместе они создают полную (непустую) строку.

Этот последний блок кода относится к случаю, когда обе строки не являются пустыми. Две строки называются sss и tts. Но чтобы избавить нас от необходимости писать head sss и tail sss для доступа к первой букве и остатку строки строки, мы просто используем @(s:ss), чтобы сообщить компилятору сохранить эти величины в переменных S и ss. Если это был С++, например, вы бы получили тот же эффект с char s = sss[0]; как первая строка вашей функции.

Лучшая ситуация заключается в том, что первые символы соответствуют s==t, а оставшаяся часть строк является допустимой k-подпоследовательностью best k sss ts /= -1. Это позволяет нам вернуть 0.

Единственная другая возможность для успеха, если текущая полная строка (sss) является допустимой k-подпоследовательностью остальной части другой строки (ts). Мы добавляем 1 к этому и возвращаемся, но делаем исключение, если разрыв будет слишком большим.

Очень важно не менять порядок этих последних пяти строк. Они - порядок в порядке убывания того, насколько хороша оценка. Мы хотим протестировать и сначала вернуть наилучшие возможности.

Ответ 2

Наивное рекурсивное решение. Бонус: = возвращаемое значение - количество способов сопоставления строки.

#include <stdio.h>
#include <string.h>

unsigned skipneedle(char *haystack, char *needle, unsigned skipmax)
{
unsigned found,skipped;

// fprintf(stderr, "skipneedle(%s,%s,%u)\n", haystack, needle, skipmax);

if ( !*needle) return strlen(haystack) <= skipmax ? 1 : 0 ;

found = 0;
for (skipped=0; skipped <= skipmax ; haystack++,skipped++ ) {
        if ( !*haystack ) break;
        if ( *haystack == *needle) {
                found += skipneedle(haystack+1, needle+1, skipmax);
                }
        }
return found;
}

int main(void)
{
char *ab = "ab";
char *test[] = {"ab" , "accb" , "abcccb" , "abcb", NULL}
        , **cpp;

for (cpp = test; *cpp; cpp++ ) {
        printf( "[%s,%s,%u]=%u \n"
                , *cpp, ab, 2
                , skipneedle(*cpp, ab, 2) );
        }

return 0;
}

Ответ 3

Решение O (p * n), где p = число возможных подпоследовательностей S в T.

Сканировать строку T и сохранить список возможных подпоследовательностей S, которые будут иметь 1. Индекс последнего символа найден и
2. Количество найденных символов

Продолжайте обновлять этот список для каждого символа T.

Ответ 4

Не уверен, что это то, о чем вы просите, но вы можете создать список символов из каждой строки и искать экземпляры одного списка в другом, а затем ((list2.length-K > list1.length) return false.

Ответ 5

Ниже представлен предлагаемый алгоритм: - O (| T | * k) средний случай

1 > сканирование T и сохранение символьных индексов в таблице Hash: -

например. S = "abc" T = "ababbc"

Записи таблицы символов: -

a = 1 3

b = 2 4 5

c = 6

2. > как мы знаем, isValidSub (S, T) = isValidSub (S (0, j), T) && & (isValidSub (S (j + 1, N), T) ||.... isValidSub (S (j + K, T), T))

a. > мы будем использовать подход снизу вверх для решения вышеуказанной проблемы.

b. > , мы будем поддерживать действительный массив Valid (len (S)), где каждая запись указывает на таблицу хешей (поясняется по мере дальнейшего решения)

c. > Начните с последнего элемента S, найдите индексы, сохраненные в соответствии с символом в таблице символов

например. в приведенном выше примере S [last] = "c"

в таблице символов c = 6

Теперь мы помещаем записи как (5,6), (4,6),.... (6-k-1,6) в таблицу Hash в Действительном (последнем)

Объяснение: - как s (6, len (S)) является допустимой подпоследовательностью, поэтому s (0,6-i) ++ s (6, len (S)) (где я находится в диапазоне (1, k + 1)) также является допустимой подпоследовательностью, если s (0,6-i) является допустимой подпоследовательностью.

3. > запустите заполнение допустимого массива от последнего до 0 элемента: -

a. > возьмем указатель из записи хэш-таблицы, соответствующей S [j], где j - текущий индекс Valid Array, который мы анализируем.

b. > Проверьте, находится ли указатель в Valid (j + 1), если он меньше, чем add (indice-i, indice), где я в диапазоне (1, k + 1) в Valid (j) Hash Table

Пример: -

S = "abc" T = "ababbc"

Итерация 1:

j = len (S) = 3

S [3] = 'c'

Таблица символов: c = 6

добавить (5,6), (4,6), (3,6) в виде K = 2 в Valid (j)

Действительный (3) = {(5,6), (4,6), (3,6)}

j = 2

итерация 2:

S [j] = 'b'

Таблица символов: b = 2 4 5

Найти 2 в Действительном (3) = > не найдено = > пропустить

Посмотрите вверх 4 в Valid (3) = > found = > add Valid (2) = {(3,4), (2,4), (1,4)}

Посмотрите вверх 5 в Valid (3) = > found = > add Valid (2) = {(3,4), (2,4), (1,4), (4,5)}

j = 1

итерация 3:

S [j] = "a"

Таблица символов: a = 1 3

Поиск 1 в Действительном (2) = > не найден

Найти 3 в Действительном (2) = > found = > остановить, поскольку это последняя итерация

КОНЕЦ

как 3 найдено в Valid (2), что означает, что существует действительная подпоследовательность, начинающаяся с T

Начало = 3

4. > Восстановите решение, перемещающееся вниз в Действительном массиве: -

пример:

Начало = 3

Поиск 3 в Действительном (2) = > найдено (3,4)

Поиск 4 в Действительном (3) = > найдено (4,6)

END

восстановленное решение (3,4,6), которое действительно является действительной подпоследовательностью

Помните (3,5,6) также может быть решением, если мы добавили (3,5) вместо (3,4) в этой итерации

Анализ сложности времени и сложности пространства: -

Сложность времени:

Шаг 1: Сканирование T = O (| T |)

Шаг 2: заполните все допустимые значения O (| T | * k), используя поиск HashTable, aprox O (1)

Шаг 3: Реконструируем решение O (| S |)

Общий средний случай Время: O (| T | * k)

Космическая сложность:

Таблица символов = O (| T | + | S |)

Действительная таблица = O (| T | * k) может быть улучшена с оптимизацией

Общее пространство = O (| T | * k)

Реализация Java: -

public class Subsequence {

private ArrayList[] SymbolTable = null;  
private HashMap[] Valid = null;
private String S;
private String T;




public ArrayList<Integer> getSubsequence(String S,String T,int K) {

    this.S = S;
    this.T = T;
    if(S.length()>T.length())
        return(null);

    S = S.toLowerCase();
    T = T.toLowerCase();

   SymbolTable = new ArrayList[26]; 
   for(int i=0;i<26;i++)
       SymbolTable[i] = new ArrayList<Integer>();

   char[] s1 = T.toCharArray();
   char[] s2 = S.toCharArray();

   //Calculate Symbol table

   for(int i=0;i<T.length();i++) {
      SymbolTable[s1[i]-'a'].add(i);       
   }

  /* for(int j=0;j<26;j++) {
       System.out.println(SymbolTable[j]);
   }
  */

   Valid = new HashMap[S.length()];

   for(int i=0;i<S.length();i++)
       Valid[i] = new HashMap<Integer,Integer >();


   int Start = -1;

   for(int j = S.length()-1;j>=0;j--) {

      int index = s2[j] - 'a';
      //System.out.println(index);

      for(int m = 0;m<SymbolTable[index].size();m++) {

          if(j==S.length()-1||Valid[j+1].containsKey(SymbolTable[index].get(m))) {

              int value = (Integer)SymbolTable[index].get(m);

              if(j==0) {
                  Start = value;
                  break;
              }

              for(int t=1;t<=K+1;t++) {
                  Valid[j].put(value-t, value);
              }
          }

      }

   }

 /*  for(int j=0;j<S.length();j++) {
       System.out.println(Valid[j]);
   }
 */  

   if(Start != -1) {        //Solution exists

       ArrayList subseq = new ArrayList<Integer>();
       subseq.add(Start);
       int prev = Start;
       int next;

       // Reconstruct solution 
       for(int i=1;i<S.length();i++) {
           next = (Integer)Valid[i].get(prev);
           subseq.add(next);
           prev = next;
       }

      return(subseq); 
   }

   return(null);


}



public static void main(String[] args) {

    Subsequence sq = new Subsequence();
    System.out.println(sq.getSubsequence("abc","ababbc", 2));

}

}

Ответ 6

Рассмотрим рекурсивный подход: пусть int f(int i, int j) обозначает минимально возможный разрыв в начале для S [i... n], соответствующий T [j... m]. f возвращает -1, если такого совпадения не существует. Здесь реализация f:

int f(int i, int j){
    if(j == m){
        if(i == n)
            return 0;
        else
            return -1;
    }
    if(i == n){
        return m - j;
    }

    if(S[i] == T[j]){
        int tmp = f(i + 1, j + 1);
        if(tmp >= 0 && tmp <= k)
            return 0;
    }
    return f(i, j + 1) + 1;
}

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

Ответ 7

Здесь реализация, которая обычно * работает в O (N) и занимает пространство O (m),, где m - длина (S).

В нем используется идея сети сюрвейера:
Представьте себе серию полюсов, связанных цепями длины k. Ахор - первый полюс в начале строки. Теперь коснитесь следующего полюса вперед, пока не найдете совпадение персонажей. Поместите этот столб. Если есть слабину, переходите к следующему символу; иначе предыдущий полюс был перетащен вперед, и вам нужно вернуться назад и переместите его на следующий ближайший матч. Повторяйте до тех пор, пока не достигнете конца или не закончите слабину.

typedef struct chain_t{
    int slack;
    int pole;
 } chainlink;


int subsequence_k_impl(char* t, char* s, int k, chainlink* link, int len)
{
  char* match=s;
  int extra = k; //total slack in the chain

  //for all chars to match, including final null
  while (match<=s+len){
     //advance until we find spot for this post or run out of chain
     while (t[link->pole] && t[link->pole]!=*match ){
        link->pole++; link->slack--;
        if (--extra<0) return 0; //no more slack, can't do it.
     }
     //if we ran out of ground, it no good
     if (t[link->pole] != *match) return 0;

    //if this link has slack, go to next pole
     if (link->slack>=0) { 
        link++; match++;
        //if next pole was already placed,
        while (link[-1].pole < link->pole) {
          //recalc slack and advance again
          extra += link->slack = k-(link->pole-link[-1].pole-1);
          link++; match++;
        }
        //if not done
        if (match<=s+len){
          //currrent pole is out of order (or unplaced), move it next to prev one
          link->pole = link[-1].pole+1; 
          extra+= link->slack = k;         
        }
     }
    //else drag the previous pole forward to the limit of the chain.
     else if (match>=s) {
        int drag = (link->pole - link[-1].pole -1)- k;
        link--;match--;
        link->pole+=drag;
        link->slack-=drag;
     }
  }
  //all poles planted.  good match
  return 1;
}

int subsequence_k(char* t, char* s, int k)
{
  int l = strlen(s);
  if (strlen(t)>(l+1)*(k+1)) 
     return -1;   //easy exit
  else {
     chainlink* chain = calloc(sizeof(chainlink),l+2);
     chain[0].pole=-1; //first pole is anchored before the string
     chain[0].slack=0;
     chain[1].pole=0; //start searching at first char
     chain[1].slack=k;
     l = subsequence_k_impl(t,s,k,chain+1,l);
     l=l?chain[1].pole:-1; //pos of first match or -1;
     free(chain);
  }
  return l;
}

* Я не уверен в большом-о. Сначала я думал, что это что-то вроде O (km + N). При тестировании он составляет менее 2N для хороших совпадений и меньше N для неудачных совпадений.
... но... есть странный вырожденный случай. Для случайных строк, выбранных из алфавита размером A, он становится намного медленнее, если k = 2A+1. Даже в этом случае это лучше, чем O (Nm), и производительность возвращается к O (N), когда k увеличивается или немного уменьшается. Gist Here, если кому-то интересно.