Problem
小b有一个字符串S和n个字符串words[1...n],现在她想知道有多少个i满足words[i]是S的子序列。
S的长度≤50000,1≤n≤5000,words[i]长度≤50.
样例解释
a,acd,ace都是abcde的子序列,但bb不是。
Solution
存一下s各个字母的位置,比较时二分查找。
Code
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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| #include<stdio.h> #include<set> #include<iostream> #include<stack> #include<cstring> #include<cmath> #include<vector> #include<algorithm> typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int mod=998244353; int mo(ll a,int p){ return a>=p?a%p:a; } inline int rd() { int x = 0, f = 1; char ch; while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } int ans,n; string s,x; int a[27][500020]; bool fun(string &cur){ int las=0,l,r,mid,anss; for(char i : cur){ l=1,r=a[i-'a'][0],anss=0; while(l<=r){ mid=l+r>>1; if(a[i-'a'][mid]>las){ r=mid-1; anss=mid;
} else{ l=mid+1; } } if(!anss){ return false; } las=a[i-'a'][anss]; } return true; } int main(){ io_opt; cin>>s>>n; for(int i=0;i<s.size();i++){ a[s[i]-'a'][++a[s[i]-'a'][0]]=i+1; } for(int i=1;i<=n;i++){ cin>>x; if(fun(x)){ ans++; } } cout<<ans<<endl; return 0; }
|