题目

leetcode， 392. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
后续挑战 :
如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

分解子问题

假设s长度是n，s是t的子序列的前提条件是前n-1个字符串也是t的子序列；
假设前n-1个子序列最后一个字符在t的位置是j，那么只要第n个字符串在j之后存在，那么就可以得到s也是t的子序列

定义递推关系

定义f(n) 返回值为is_sub和end_index，is_sub表示为s的前n个字符是否是t的子序列，end_index表示第n个字符在t的位置
has(begin_index, c) 返回字符c是否在t的以begin_index开始的后面字符串里。

is_sub, end_index = f(n-1)
f(n) = is_sub && has(end_index + 1, s[n])

自底向上实现

class Solution {

public:

bool isSubsequence(string s, string t) {
    int end_index;
    return isSubsequence((char*)s.c_str(), s.size(), (char*)t.c_str(), t.size(),end_index);
}

bool isSubsequence(char* s, int s_len, char* t, int t_len, int& end_index){
    if(s_len==0){
        return true;
    }

    int last_end_index = -1;
    if(isSubsequence(s, s_len-1, t, t_len, last_end_index)){
        if(has(t, t_len, last_end_index+1, s[s_len-1], last_end_index)){
            end_index = last_end_index;
            return true;
        }else{
            return false;
        }
    }else{
        return false;
    }
}

bool has(char* t, int t_len, int offset, char c, int &end_index){
    if(t_len <= offset){
        return false;
    }
    end_index = offset;
    char t_c = t[end_index];
    while(t_c){
        if(t_c == c){
            return true;
        }
        end_index++;
        t_c = t[end_index];
    }
    return false;
}

};