验证子序列(动态规划)
题目描述：
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S 1 , S 2 , . . . , S k S_1, S_2, ... , S_k S1,S2,...,Sk 其中 k ≥ 10 k\ge10 k≥10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码?
思路
这是一道基础的动态规划练习题,考虑到有 1 0 9 10^9 109以上数量级的输入，则不可能遍历这么多次T字符串，为了节省时间，我们可以对T进行预处理，转而遍历较短的S串。那么我们需要知道，在T的某个位置i后的某一个字符j在哪个位置第一次出现，如此可以直接跳转到那个位置，继续匹配S串的下一个字符。
由于需要知道下一个字符j在哪里出现，那么显然我们需要从后往前遍历，并不断更新j的合理位置，则dp数组如下定义：
d
p
[
i
]
[
j
]
,
i
表示位置，
j
表示字符
d
p
[
i
]
[
j
]
=
{
i
t
[
i
]
=
j
d
p
[
i
+
1
]
[
j
]
t
[
i
]
!
=
j
dp[i][j],i表示位置，j表示字符\\ dp[i][j]=\begin{cases} i& t[i]=j\\ dp[i+1][j]&t[i]!=j \end{cases}
dp[i][j],i表示位置，j表示字符dp[i][j]={idp[i+1][j]t[i]=jt[i]!=j
如果当前位置是字符j，则更新为当前位置，如果不是，则更新为后一位的j字符位置，这就是转移方程。
在后续验证的时候，可以用start记录开始匹配的位置，每次匹配完成都要在匹配后的下一个位置开始，否则可能会无限循环，给出错误的判断。
代码实现
bool isSubsequence(string s, string t) {
int len =t.size();//考虑到题目所说的巨量s，可以预先对t进行处理
if(len<s.size()) return false;
vector<vector<int>>dp (len+1,vector<int>(26,-1));
//dp的思路：从后往前，因为我们想要记录某一字母在后面第一次出现的位置
//对于dp[i][j]，i表示位置，j表示字符，如果t[i]=j,则dp[i][j]=i
//如果t[i]!=j,dp[i][j]=dp[i+1][j]（i位置不为j，则值为后一位的值），依次dp即可
//注意从后面开始
int index;
for(int i =len-1;i>=0;i--){
index = t[i]-'a';
dp[i][index]=i;
for(int j =0;j<26;j++){
if(j!=index) dp[i][j]=dp[i+1][j];
}
}
int alpha,start=0;
for(int i =0;i<s.size();i++){
alpha=s[i]-'a';
if(dp[start][alpha]==-1) return false;
start = dp[start][alpha]+1;//跳过自己，否则遇到连续的相同字符会出错
}//s从头开始比较，更新为最近的位置，如果为-1，说明不匹配
return true;
}