fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define db long double
  10. #define onBit(mask , i) (mask | (1 << i))
  11. #define offBit(mask , i) (mask & (~(1 << i)))
  12.  
  13. const long long INF = 1e16;
  14. const int N = 2e5 + 7;
  15. string t , s;
  16. int n , q , _lext[N] , lext[N][27];
  17.  
  18. void inp(){
  19. 	cin >> n >> q;
  20. 	cin >> s;
  21. 	s = "a" + s;
  22. }
  23.  
  24. void ktao(){
  25. 	for (int i = n ; i >= 0 ; --i){
  26. 		for (int j = 0 ; j < 26 ; ++j){
  27. 			if (_lext[j] == 0) continue;
  28. 			lext[i][j] = _lext[j];
  29. //			cout << i << " " << char(j + 'a') << " " << lext[i][j] << '\n';
  30. 		}
  31. 		_lext[s[i] - 'a'] = i;
  32.  
  33. 	}
  34. }
  35.  
  36. bool check(int k){
  37. 	int i = lext[0][t[0] - 'a'];
  38. 	if (i == 0) return 0;
  39. 	int cnt = 1;
  40. 	while (i <= n){
  41. 		if (cnt == t.size()) break;
  42. 		if (i + k > n) return 0;
  43. 		i = lext[i + k - 1][t[cnt] - 'a'];
  44. 		if (i == 0) return 0;
  45. 		++cnt;
  46. 	}
  47. 	return 1;
  48. }
  49.  
  50. void solve(){
  51. 	ktao();
  52. 	while (q--){
  53. 		cin >> t;
  54. 		int l = 1 , r = n , mid , res = -1;
  55. 		while (l <= r){
  56. 			mid = (l + r) >> 1;
  57. 			if (check(mid)){
  58. 				res = mid;
  59. 				l = mid + 1;
  60. 			}
  61. 			else r = mid - 1;
  62. 		}
  63. 		cout << res << '\n';
  64. 	}
  65. }
  66.  
  67. int main(){
  68. //	freopen("xhmax.inp" , "r" , stdin);
  69. //	freopen("xhmax.out" , "w" , stdout);
  70.     faster;
  71.     inp();
  72.     solve();	
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/jGN2yp
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

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!