Snapper_001

Untitled

Jul 21st, 2022
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.67 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  3. #define pb push_back
  4. #define all(x) (x).begin(),(x).end()
  5. #define ll long long
  6. #define ld long double
  7. #define eps 1e-9
  8. #define sz(a) (ll)(a).size()
  9. #define ppc __builtin_popcount
  10. #define ppcll __builtin_popcountll
  11. #define endl "\n"
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. const ld PI = acos(-1.0);
  15. const int MOD = 1e9 +7;
  16. const ll INF = 1e18;
  17. // if(abs(a-b)<eps) --> if(a==b)
  18. // fixed << setprecision(n) -->printing decimal till n
  19. // hypot(a ,b) --> sqrt(a^2 + b^2)
  20. using namespace std;
  21.  
  22. void solve(){
  23. string s,t1;
  24. cin>>s>>t1;
  25. vector<vector<ll>>dp(26);
  26. for(int i=0;i<sz(s);i++){
  27. dp[s[i]-'a'].pb(i);
  28. }
  29.  
  30. ll ind =0;
  31. ll copies =1;
  32. for(int i=0;i<sz(t1);i++){
  33. if(dp[t1[i]-'a'].size()==0){
  34. cout<<-1<<endl;
  35. return;
  36. }
  37.  
  38. auto it = lb(all(dp[t1[i]-'a']) , ind);
  39. if(it==dp[t1[i]-'a'].end()){
  40. //again chekcing
  41. ind =0;
  42. copies++;
  43. auto it1 = lb(all(dp[t1[i]-'a']) , ind);
  44. ind = *it1;
  45. }
  46. else{
  47. ind = *it;
  48. }
  49. }
  50.  
  51. cout<<copies*sz(s) - sz(s) + ind+1 <<endl;
  52. }
  53.  
  54. int main(){
  55. IO;
  56. ll t =1;
  57. // cin>>t;
  58. for(int i=1;i<=t;i++){
  59. // cout<<"Case #"<<i<<": ";
  60. solve();
  61. }
  62. return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment