Readme

792.Number-of-Matching-Subsequences

传统的方法，利用双指针挨个比较s和word，那么时间复杂度就是o(ST)，其中S是s的长度，T是words的总长度。本题的考点在于s的长度很大时，时间复杂度如何优化。

解法1：二分搜索

我们可以提前预处理s，将每个字符出现的位置分别归类，即pos[ch]包含了s里字符ch所在的位置（可能有若干个）。假设我们在查看word[0]='a'的时候，直接从pos['a']里面找最早的位置i。再查看word[1]='b'的时候，又从pos['b']里面找第一个大于等于i的位置j。再查看word[1]='c'的时候，从pos['c']里面找第一个大于等于j的位置k。依次类推。如果遇到某个word的字符ch，但是pos[ch]里面没有大于等于某个期望位置的元素时，那么这个word就不是s的子序列了。

时间复杂度是o(TlogS)，因为在word中每处理一个字符，都需要在pos[ch]里进行一次二分查找。

解法2：状态机

我们提前处理s，得到next[i][ch]，表示i位置之后下一个出现字符ch的位置是哪里；如果再没有出现过ch，那么标记-1. next数组的预处理是从后往前进行的，时间是o(26S).

在处理word时，我们通过next[0][word[0]]，找到下一个出现word[0]的位置i。再通过next[i][word[1]]，找到下一个出现word[1]的位置j。再通过next[i][word[2]]，找到下一个出现word[2]的位置k。依次类推，如果word的每一个字符都能在next中找到，那么就OK。否则如果遇到类似next[k][word[3]]==-1，就说明该字符找不到，即word不是s的子序列。

时间复杂度是o(T).