字元串的子序列

給定兩個隻包含小寫字母的字元串，分别為s和t。

現在将字元串s進行無限次拼接得到s′，問字元串t是否是s′的一個子序列。

如果是，輸出s′中的最後一個位置；否則輸出-1。

輸入格式

輸入兩行，每行為一個隻包含小寫字母的字元串。

輸出格式

輸出一個整數。

測試樣例一

rainsure
rraaiinn
           

36
           

測試樣例二

abcdefg
bcdk
           

-1
           

思路：

開26個桶（這裡的桶即set） ，将s字元串中字元的下标索引放入桶中；周遊t字元串，如果該字元對應的桶不為空，找比上一個位置嚴格大的（也就是保證能在s字元串中從上一個位置一直往後找），如果往後找到最後了還是沒有，則往後拼接一個s，cnt++,（其實就是再重新到s的開頭往後繼續進行查找），最後t周遊完了，代表子序列比對完成 ，輸出cnt個完整的s的長度+最後一個位置下标索引+1即為所求。如果在中間周遊t的過程中，遇到該字元對應的桶是空的，就輸出-1。

一開始做逾時真的讨厭，後來又答案錯誤更是讨厭。

正确解法：外層字元串周遊時間複雜度為m，内層利用upper_bound二分查找時間複雜度為logn

總得大概為mlogn，更優化一點

關于lower_bound( )和upper_bound( )的常見用法

AC:

#include <bits/stdc++.h>

using namespace std;

set<int> p[26];
int lastp=-1,cnt;

int main()
{
    string s,t;
    cin>>s>>t;
    for(int i=0;i<s.length();i++) p[s[i]-'a'].insert(i);
    for(int i=0;i<t.length();i++)
    {
        int key=t[i]-'a';
        if(p[key].size())
        {
            auto it=p[key].upper_bound(lastp);
            if(it==p[key].end())
            {
                cnt++;
                it=p[key].begin();
            }
            if(i==t.length()-1)
            {
                cout<<cnt*s.length()+(*it)+1<<endl;
                return 0;
            }
            lastp=*it;
        }
        else
        {
            cout<<"-1"<<endl;
            return 0;
        }
    }
}
           

WA：

#include<bits/stdc++.h>
using namespace std;
//運作逾時
bool isSubsequence(string s, string t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        return i == n;
    }

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin>>s>>t;
    string sum=s;
    int flag=0,flag1=0;
    int id;
    for(int i=0;i<t.size();i++)
    {

    }
    for(int i=1;;i++){
        id=i;
        if(isSubsequence(t,sum))
        {
            flag=1;
            break;
        }
        sum+=s;
    }
   // cout<<id<<" "<<s.size()<<endl;
    int num;
   for(int i=sum.size()-1;i>=0;i--)
   {
       if(sum[i]==t[t.size()-1])
       {
           num=sum.size()-i-1;
           break;
       }
   }
   //cout<<num<<endl;
   cout<<id*s.size()-num;

}
//答案錯誤
bool isSubsequence(string s, string t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        return i == n;
}
int main()
{
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    string s, t,str;
    cin >> s >> t;
    int j = 0;
    int cnt = 1;
    int num=0;
    vector<char> a,b;
    for(int i=0;i<t.size();i++)
    {
        a.push_back(t[i]);
    }
    vector<char>::iterator it1;
    for(auto it=++a.begin();it!=a.end();)
    {
        it1=find(a.begin(),it,*it);
        if(it1!=it)
            it=a.erase(it);
        else
            it++;
    }
    for(auto it=a.begin();it!=a.end();it++)
        str+=*it;
    if(!isSubsequence(str,s))
    {
        cout<<"-1";
        return 0;
    }
    for(int i = 0; i < t.size(); i++)
    {
        while(t[i] != s[j])
        {
            if(j == s.size() - 1)
            {
                cnt++;
                j = -1;
            }
            j++;
            num++;
        }
        j++;
        num++;
        continue;

    }
        cout<<num;

}