fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12.  
  13. int n, m;   
  14. string s, t; 
  15.  
  16. int nxt[N][26]; // nxt[i][c] = Vị trí i' gần nhất > i sao cho s[i'] = c
  17.  
  18. void precompute() {
  19. 	for (int c = 0; c <= 25; c++) nxt[n][c] = n + 1;  
  20.  
  21. 	for (int i = n - 1; i >= 0; i--) {
  22. 		for (int c = 0; c <= 25; c++) nxt[i][c] = nxt[i + 1][c]; 
  23. 		nxt[i][s[i + 1] - 'a'] = i + 1; 
  24. 	}
  25. }
  26.  
  27. int main() {
  28. 	ios::sync_with_stdio(false); 
  29. 	cin.tie(nullptr); 	
  30. 	cin >> s; n = s.size(); 
  31. 	cin >> t; m = t.size();  
  32. 	s = ' ' + s;   
  33. 	t = ' ' + t;  
  34.  
  35. 	precompute(); 
  36.  
  37. 	int i = 0, cnt = 1;
  38. 	bool exist = true;  
  39. 	for (int j = 1; j <= m; j++) {
  40. 		int c = t[j] - 'a';  
  41. 		if (nxt[i][c] <= n) {
  42. 			i = nxt[i][c]; 
  43. 		}
  44. 		else {
  45. 			++cnt;  
  46. 			i = 0;  
  47. 			i = nxt[0][c];  
  48. 			if (i == n + 1) {
  49. 				exist = false; 
  50. 				break; 
  51. 			}
  52. 		}
  53. 	}  
  54.  
  55. 	if (!exist) {
  56. 		cout << -1 << '\n'; 
  57. 	}
  58. 	else {
  59. 		ll ans = 1ll * (cnt - 1) * n + i; 
  60. 		cout << ans << '\n'; 
  61. 	}
  62. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
contest
son
stdout
copy 
10
https://ideone.com/IhAu5O
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!