字符串中出现子序列

本文介绍了字符串中出现子序列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出2个类似bangalore和blr的字符串，返回一个字符串是否显示为另一个字符串的子序列。上面的情况返回true，而bangalore和brl返回false。

Given 2 strings like bangalore and blr, return whether one appears as a subsequence of the other. The above case returns true whereas bangalore and brl returns false.

推荐答案

贪婪策略应该可以解决此问题。

Greedy strategy should work for this problem.

• 在大字符串（* b * angalore）中查找可疑子字符串（blr）的首字母
• 查找第二个字母从第一个字母的索引加一个（anga * l * ore）开始
• 查找第二个字母，从第二个字母的索引加一个（o * r * e）
• 继续，直到您不再在字符串中找到下一个blr字母（不匹配），或者子序列中的字母用完（您有匹配项）为止。 / li>

• Find the first letter of the suspected substring (blr) in the big string (*b*angalore)
• Find the second letter starting at the index of the first letter plus one (anga*l*ore)
• Find the third letter starting at the index of the second letter plus one (o*r*e)
• Continue until you can no longer find the next letter of blr in the string (no match), or you run out of letters in the subsequence (you have a match).

以下是C ++中的示例代码：

Here is a sample code in 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; }