fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. using namespace std;
  6. const int MX = 500010, ALPH = 26, INF = 1e9;
  7. int b[MX][ALPH], key = 1;
  8. int s[MX];
  9.  
  10. void addWord(string a) {
  11. 	int cur = 0;
  12. 	for (int i = 0; i < a.size(); i++) {
  13. 		int next = b[cur][(int)a[i]-'a'];
  14. 		if (next == INF) {
  15. 			b[cur][(int)a[i]-'a'] = key;
  16. 			s[key] = (int)a.size();
  17. 			cur = key++;
  18. 		}
  19. 		else {
  20. 			s[next] = min(s[next], (int)a.size());
  21. 			cur = next;
  22. 		}
  23. 	}
  24. }
  25.  
  26. int main() {
  27. 	int n; cin >> n;
  28. 	for (int i = 0; i < MX; i++) for (int j = 0; j < ALPH; j++) {
  29. 		b[i][j] = INF;
  30. 		s[i] = INF;
  31. 	}
  32. 	int minLength = INF;
  33. 	for (int i = 0; i < n; i++) {
  34. 		string a; cin >> a;
  35. 		addWord(a);
  36. 		minLength = min(minLength, (int)a.size());
  37. 	}
  38. 	int q; cin >> q;
  39. 	for (int i = 0; i < q; i++) {
  40. 		string a; cin >> a;
  41. 		int len = a.size(), ans = minLength+len, cur = 0;
  42. 		for (int i = 0; i < a.size(); i++) {
  43. 			int next = b[cur][(int)a[i]-'a'];
  44. 			if (next == INF) {
  45. 				break;
  46. 			}
  47. 			else {
  48. 				cur = next;
  49. 			}
  50. 			ans = min(ans, len+s[cur]-2*(i+1));
  51. 		}
  52. 		cout << ans << '\n';
  53. 	}
  54. 	return 0;
  55. }
Time limit exceeded #stdin #stdout 5s 56208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/35zUcs
language:
C++14 (gcc 8.3)
created:
7 years 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!