Удалить все вхождения подстрок из строки

Question

С учетом строки S и набора подстрок n. Удалите все экземпляры этих n подстрок из S, так что S имеет минимальную длину и выводит эту минимальную длину.

Пример 1

S = ccdaabcdbb 
n = 2 
substrings = ab, cd 

Выход

2 

Пояснение:

ccdaabcdbb -> ccdacdbb -> cabb -> cb (length=2) 

Пример 2

S = abcd 
n = 2 
substrings = ab,bcd 

Выход

1 

Как решить эту проблему?

Answer 1

Простого Brute-force search алгоритм:

• Для каждой подстроки, попробовать все возможные способы, чтобы удалить его из строки, то рекурсии.

В Pseudocode:

def min_final_length (input, substrings): 
    best = len(input) 
    for substr in substrings: 
     beg = 0 
     // find all occurrences of substr in input and recurse 
     while (found = find_substring(input, substr, from=beg)): 
      input_without_substr = input[0:found]+input[found+len(substr):len(input)] 
      best = min(best, min_final_length(input_without_substr,substrings)) 
      beg = found+1 
    return best 

Пусть сложность будет F(S,n,l), где S является длиной строки input, n является мощностью множества substrings и l является «характерной длиной» подстрок. Тогда

F(S,n,l) ~ n * (S * l + F(S-l,n,l)) 

Похоже, это самое O(S^2*n*l).

Answer 2

Если вы используете сырую производительность, а ваша строка очень велика, вы можете сделать лучше, чем грубая сила. Используйте суффикс trie (например, Ukkonnen trie), чтобы сохранить вашу строку. Затем найдите каждую подстроку (которую мы сделали в O (m) time, m - длина подстроки) и сохраните смещения подстроками и длиной в массиве. Затем используйте значения смещений и длины для фактического удаления подстрок, заполнив эти области с помощью \ 0 (в C) или другого символа-заполнителя. При подсчете всех символов, отличных от Null, вы получите минимальную длину строки.

Это будет обрабатывать перекрывающуюся подстроку, например. скажем, ваша строка «abcd», и у вас есть две подстроки «ab» и «abcd».

Answer 3

Следующее решение будет иметь сложность O (M * N), где М = Len (S), и п является числом подстроки

def foo(S, sub): 
    i = 0 
    while i < len(S): 
     for e in sub: 
      if S[i:].startswith(e): 
       S = S[:i] + S[i+len(e):] 
       i -= 1 
       break 
     else: i += 1 
    return S, i 

Answer 4

Я решил его с помощью синтаксического дерева + дп.
Сначала вставьте свои подстроки в три.Затем определите состояние dp - это некоторая строка, пройдите через эту строку и рассмотрите каждую i (для i = 0 .. s.length()) как начало некоторой подстроки. пусть j = i и increment j, если у вас есть суффикс в trie (который определенно приземляет вас по крайней мере на одну подстроку и может быть больше, если у вас есть общий суффикс между некоторой подстрокой, например «abce» и «abdd»,), всякий раз, когда вы сталкиваетесь с завершением некоторой подстроки, переходите к решению новой подзадачи и найдите минимум между всеми сокращениями подстроки.

Вот мой код для этого. Не беспокойтесь о длине кода. Просто прочитайте функцию решения и забудьте о пути, я включил его для печати созданной строки.

struct node{ 
    node* c[26]; 
    bool str_end; 
    node(){ 
     for(int i= 0;i<26;i++){ 
      c[i]=NULL; 
     } 
     str_end= false; 
    } 
}; 
class Trie{ 
public: 
    node* root; 
    Trie(){ 
     root = new node(); 
    } 
    ~Trie(){ 
     delete root; 
    } 
}; 
class Solution{ 
public: 
    typedef pair<int,int>ii; 
    string get_str(string& s,map<string,ii>&path){ 
     if(!path.count(s)){ 
      return s; 
     } 
     int i= path[s].first; 
     int j= path[s].second; 
     string new_str =(s.substr(0,i)+s.substr(j+1)); 
     return get_str(new_str,path); 
    } 
    int solve(string& s,Trie* &t, map<string,int>&dp,map<string,ii>&path){ 
     if(dp.count(s)){ 
      return dp[s]; 
     } 
     int mn= (int)s.length(); 
     for(int i =0;i<s.length();i++){ 
      string left = s.substr(0,i); 
      node* cur = t->root->c[s[i]-97]; 
      int j=i; 
      while(j<s.length()&&cur!=NULL){ 
       if(cur->str_end){ 
        string new_str =left+s.substr(j+1); 
        int ret= solve(new_str,t,dp,path); 
        if(ret<mn){ 
         path[s]={i,j}; 
        } 
       } 
       cur = cur->c[s[++j]-97]; 
      } 
     } 
     return dp[s]=mn; 
    } 
    string removeSubstrings(vector<string>& substrs, string s){ 
     map<string,ii>path; 
     map<string,int>dp; 
     Trie*t = new Trie(); 
     for(int i =0;i<substrs.size();i++){ 
      node* cur = t->root; 
      for(int j=0;j<substrs[i].length();j++){ 
       if(cur->c[substrs[i][j]-97]==NULL){ 
        cur->c[substrs[i][j]-97]= new node(); 
       } 
       cur = cur->c[substrs[i][j]-97]; 
       if(j==substrs[i].length()-1){ 
        cur->str_end= true; 
       } 
      } 
     } 
     solve(s,t,dp,path); 
     return get_str(s, path); 
    } 
}; 

int main(){ 
    vector<string>substrs; 
    substrs.push_back("ab"); 
    substrs.push_back("cd"); 
    Solution s; 
    cout << s.removeSubstrings(substrs,"ccdaabcdbb")<<endl; 
    return 0; 
}