字符串中的子序列出現

給定2個字符串，如bangalore和blr，返回一個字符串是否出現在另一個字符串的子序列中。上述情況返回true，而bangalore和brl返回false。字符串中的子序列出現

2011-12-22 princess of persia

這功課嗎？ – Blender 2011-12-22 04:21:15

不是沒有作業，我想到的第一件事是後綴trie，但不知道它是否是一個好選擇，所以想知道什麼是第一個出現在他人頭腦中的東西？ – 2011-12-22 04:31:18

貪婪策略應該適用於這個問題。

查找可疑子（BLR）的大串的第一個字母（* B * angalore）
找到第二個字母開始的第一個字母的指數加一（ANGA * L *礦點）
查找從第二個字母加上一個索引開始的第三個字母（o * r * e）
繼續，直到找不到字符串中的下一個字母blr（不匹配），或者您用完子序列中的字母（你有一個匹配）。

這裏是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; 
}

來源

2011-12-22 04:20:43 dasblinkenlight

我猜這是不可能的比O（n）好？ – 2011-12-22 04:33:06

@princessofpersia不，沒有預處理。如果你有一個很大的文本，並且需要反覆查詢它的子串，我認爲你可以對它進行一些優化：對於字母表中的每個字母，在文本中存儲它的出現的排序列表。然後你可以在'O（K * logN）'中進行搜索，其中'K'是子字符串中的字母數，'N'是文本中的字母數。 – dasblinkenlight 2011-12-22 04:37:02

logN用於二進制搜索的字符串？ – 2011-12-22 04:42:39

-1

查找longest common subsequence的長度。如果它等於小字符串的長度，則返回true

來源

2011-12-22 11:02:19 MBo

+14

這就像拿着大錘來殺死蒼蠅一樣！ LCS是O（N * M），它會比貪婪慢，特別是當沒有匹配時。 – dasblinkenlight 2011-12-22 11:25:33

是的，你是對的。 – MBo 2011-12-22 12:28:36

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

來源

2013-10-11 05:59:12

O（N）解，其中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; 
}

來源

2017-03-10 07:18:42 leo

字符串中的子序列出現

回答

相關問題