牛牛与字符串题解

牛牛现在有两个字符串s和t，这两个字符串只包含小写字母。
牛妹有一个空字符串z，牛妹每次可以从牛牛那里取s字符串的任意一个子序列加到z字符串的后面。牛妹可以一直从s字符串中取出子序列(取过的子序列也可以再取)，而不会对s字符串造成任何影响。
现在牛妹问牛牛，最少要取多少次才能让z字符串与t字符串相等？
牛牛不知道该如何解答，他想请你帮他写一个程序，返回使z字符串与t字符串相等牛妹最少需要取的次数，如果牛妹不可能完成，请返回-1。

时间复杂度： 空间复杂度：

解题思路：
为了解题方便，我们首先可以使用vector存s中26个字母的下标位置，然后在t中遍历查找，用p记录查到上一个字符在字符串s中的位置。
如果在t内有一个字符没有在s中，那就说明牛妹无法构造成功，返回-1；
如果当前的p大于等于这个字符在s中出现的最后一个位置，说明这一次子序列已经到头了，不能往后继续遍历了，这时我们需要重新开始一次从头取子序列，让ans++，更新p，让p等于当前字符在s中出现的第一个位置；如果不是，我们可以使用二分查找（二分查找有很多方法，可以手写一个，我这里为了方便用了c++库里自带的），查找大于p出现的第一个该字符的位置，使p等于这个位置。
将以上思想，用代码实现，如下：

inline int gid(char s)
{
    return s - 'a';
}

/**
 * 返回使z字符串与t字符串相等牛妹最少需要取多少次，如果牛妹不可能完成，请返回-1
 * @param s string字符串 代表字符串s
 * @param t string字符串 代表字符串t
 * @return int整型
 */
int solve(string s, string t)
{
    // write code here
    vector<int> v[26];
    int siz[26];
    memset(siz, 0, sizeof siz);
    int lens = s.size(), lent = t.size(), i, j, d, p = -1, pd, ans = 1;
    for (i = 0; i < 26; i++)
        v[i].clear();
    for (i = 0; i < lens; i++)
    {
        d = gid(s[i]);
        v[d].push_back(i);
        siz[d]++;
    }
    for (i = 0; i < lent; i++)
    {
        d = gid(t[i]);
        if (siz[d] == 0)
            return -1;
        if (p >= v[d][siz[d] - 1])
        {
            ans++;
            p = v[d][0];
        }
        else
        {
            pd = upper_bound(v[d].begin(), v[d].end(), p) - v[d].begin();
            p = v[d][pd];
        }
    }
    return ans;
}