Sự xuất hiện chuỗi phụ trong một chuỗi

Question

Cho 2 chuỗi như bangalore và blr, trả lại xem chuỗi có xuất hiện như là một chuỗi của chuỗi kia hay không. Trường hợp trên trả về true trong khi bangalore và brl trả về false.

Answer 1

Chiến lược tham lam nên hoạt động cho vấn đề này.

• Tìm chữ cái đầu tiên của chuỗi con nghi ngờ (BLR) trong chuỗi lớn (* b * angalore)
• Tìm chữ cái thứ hai bắt đầu từ chỉ số của chữ cái đầu tiên cộng với một (Ương Già * l * quặng)
• Tìm chữ cái thứ ba bắt đầu từ chỉ mục của chữ cái thứ hai cộng một (o * r * e)
• Tiếp tục cho đến khi bạn không thể tìm thấy chữ cái tiếp theo của chuỗi trong chuỗi (không khớp) hoặc bạn chạy ra khỏi các chữ cái trong các subsequence (bạn có một trận đấu).

Đây là một mẫu mã trong 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

Tìm chiều dài của longest common subsequence. Nếu giá trị này bằng với độ dài của chuỗi nhỏ, hãy trả về true

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

Giải pháp O (N), trong đó N là độ dài của chuỗi con.

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; 
}