(CF1295C)Obtain The String

发表于 分类于 ，

原题链接

思路:

贪心 + 二分 + 前缀和

贪心指对于字符串 b 中的每个字母，选择串 a 中” 可选区域” 中最前面那个. “可选区域” 由前一个字母决定。若可选区域中没有则答案 + 1 并在整个串 a 中寻找， 若串 a 也没有则无解.

其中，“选择串 a 中’可选区域’中最前面那个” 由二分 + 前缀和完成. 对于每个字母统计区间 [1, n] 中该字母出现次数， 二分时便可通过前缀和判断某区间是否有所要寻找的字母.

时间复杂度：预处理 O (n)(可能常数较大), 计算 O (mlogn), 其中 n,m 分别为串 a 与串 b 的长度.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
const int Mn(100500);
int ise[Mn][30];    //前缀和
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        string a,b;
        cin >> a >> b;
        /*----预处理----*/
        memset(ise[0],0,sizeof ise[0]);
        for(int i(1);i<=a.size();++i)
        {
            memcpy(ise[i],ise[i-1],sizeof ise[i]);
            ++ise[i][a[i-1]-'a'];	//统计字母个数
        }
        memcpy(ise[a.size()+1],ise[a.size()],sizeof ise[0]);
        for(int i(0);i<30;++i)
            ++ise[a.size()+1][i];	//在最后一位的后面+1是为了方便处理边界
        int p(0);	//上一个字母被找到的位置, 用来确定"可选区域"
        int ans(1);	//答案
        for(int i(0);i<b.size();++i)
        {
            if(ise[a.size()][b[i]-'a']==0)	//若串a中没有该字母则直接退出
            { ans = -1; break; }
            else if(ise[a.size()][b[i]-'a']==ise[p][b[i]-'a'])	//若可选区域中没有该字母答案+1
            { ++ans; p=0; }
            /*----二分----*/
            int l(p+1),r(a.size()+1);	//在"可选区域"内查找
            while(r-l>3)	//用于处理边界的技巧, 当区间长度小于某值时直接暴力
            {
                int m((l+r)>>1);
                if(ise[m][b[i]-'a']!=ise[l-1][b[i]-'a'])	r = m+1;
                else l = m+1;
            }
            for(int j(l);j<r;++j)
                if(ise[j][b[i]-'a']!=ise[j-1][b[i]-'a'])
                { p = j; break; }
        }
        printf("%d\n",ans);
    }	
    return 0;
}