文字列内でのサブシーケンスの発生

Question

bangaloreとblrのような2つの文字列がある場合、一方が他方のサブシーケンスとして表示されるかどうかを返します。上記の場合はtrueを返しますが、bangaloreとbrlはfalseを返します。

Answer 1

この問題では貪欲な戦略が有効です。

• 大きな文字列内の疑いのサブ（BLR）の最初の文字を検索（* b *のangalore）
• は、最初の文字のインデックスプラスワン（ANGAの*のL *鉱石から始まる第二の手紙を探します）
• あなたは、もはや文字列（マッチしない）にBLRの次の文字を見つけることができるまで続行しない
• ）は、第2の文字のインデックスプラスワン（Oの*のR *電子から始まる3番目の文字を検索し、か部分列の文字がなくなります（あなたには一致します）。ここで

C++のサンプルコードです：

#include <iostream> 
#include <string> 
using namespace std; 

int main() { 
    string txt = "quick brown fox jumps over the lazy dog"; 
    string s = "brownfoxzdog"; 
    int pos = -1; 
    bool ok = true; 
    for (int i = 0 ; ok && i != s.size() ; i++) { 
     ok = (pos = txt.find(s[i], pos+1)) != string::npos; 
    } 
    cerr << (ok ? "Found" : "Not found") << endl; 
    return 0; 
} 

Answer 2

はlongest common subsequenceの長さを検索します。それは小さな文字列の長さに等しい場合、Nは、サブストリングの長さである真

Answer 3

// Solution 1 
public static boolean isSubSequence(String str1, String str2) { 
    int i = 0; 
     int j = 0; 
     while (i < str1.length() && j < str2.length()) { 
      if (str1.charAt(i) == str2.charAt(j)) { 
       i++; 
       j++; 
      } else { 
       i++; 
      } 
     } 
    return j == str2.length(); 
} 

// Solution 2 using String indexOf method 
public static boolean isSubSequenceUsingIndexOf(String mainStr, String subStr) { 
    int i = 0; 
    int index = 0; 
    while(i<subStr.length()) { 
     char c = subStr.charAt(i); 
     if((index = mainStr.indexOf(c, index)) == -1) { 
      return false; 
     } 
     i++; 
    } 

    return true; 
} 

Answer 4

O（N）溶液を、返します。

bool subsequence(string s1, string s2){ 
    int n1 = s1.length(); 
    int n2 = s2.length(); 

    if(n1 > n2){ 
     return false; 
    } 

    int i = 0; 
    int j = 0; 
    while(i < n1 && j < n2){ 
     if(s1[i] == s2[j]){ 
      i++; 
     } 
     j++; 
    } 

    return i == n1; 
}