牛牛的字符串游戏

显然我们得按顺序获得目标t的每个字符。对于我们可以在s中找到这么一个子序列。显然如果找到尾巴还是没有需要的。就得从s[0]开始重新开始顺序找。(然后答案递增,因为表示要重新开始加一个子序列了) 所以不能直接找。所以我们可以另外开一个数组表示在i-1位置,如果要找下一个紧接着的j的话,需要到哪个位置找。
复杂度O(26*n)

int nxt[26][100010];
class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return int整型
     */
    int string(string s, string t) {
        int n = s.size();
        int m = t.size();
        for(int i = 0; i < 26; i ++)
            for(int j = 0; j <= n; j ++)
                nxt[i][j] = n;
        for(int i = 0; i < 26; i ++)
            for(int j = n - 1; j >= 0; j --)
                nxt[i][j] = (s[j] == 'a' + i ? j : nxt[i][j + 1]);
        int cur = 0;
        int ans = 1;
        for(int i = 0; i < m; i ++)
        {
            int x = t[i] - 'a';
            if(nxt[x][0] == n) return -1;
            if(nxt[x][cur] == n) {ans ++; cur = 0;}
            cur = nxt[x][cur] + 1;
        }
        return ans;
    }
};