fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const int MAXN = 300001;
  25. const int sigma = 26;
  26.  
  27. int to[MAXN][sigma];
  28. int dp[MAXN];
  29. int sz = 1;
  30.  
  31. void add_str(string s)
  32. {
  33.     int cur = 0;
  34.     for(int i = 0; i < s.length(); i++)
  35.     {
  36. 		char c = s[i];
  37. 		dp[cur] = min(int(s.length()), dp[cur]);
  38.         if(!to[cur][c - 'a'])
  39.         {
  40.             to[cur][c - 'a'] = sz++;
  41.         }
  42.         cur = to[cur][c - 'a'];
  43.     }
  44.     dp[cur] = min(int(s.length()), dp[cur]);
  45. }
  46.  
  47. const int INF = 1000000000;
  48.  
  49. int calc(string &s)
  50. {
  51. 	int ans = s.length() + dp[0];
  52. 	int cur = 0;
  53. 	for(int i = 0; i < s.length(); i++)
  54. 	{
  55. 		char c = s[i];
  56. 		cur = to[cur][c - 'a'];
  57. 		if(cur == 0) break;
  58. 		ans = min(ans, int(s.length()) + dp[cur] - 2*(i+1));
  59. 	}
  60. 	return ans;
  61. }
  62.  
  63. int main()
  64. {
  65. 	ios_base::sync_with_stdio(0); cin.tie(0);
  66. 	for(int i = 0; i < MAXN; i++) dp[i] = INF;
  67. 	int n; cin >> n;
  68. 	for(int i = 0; i < n; i++)
  69. 	{
  70. 		string s; cin >> s;
  71. 		add_str(s);
  72. 	}
  73. 	//cerr<<"DP 0 = "<<dp[0]<<'\n';
  74. 	int q; cin >> q;
  75. 	while(q--)
  76. 	{
  77. 		string s; cin >> s;
  78. 		cout << calc(s) << '\n';
  79. 	}
  80. }
  81.  
Time limit exceeded #stdin #stdout 5s 35112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kdZkbk
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!