fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int trie[800010][3], k, ans;
  6. long long dp[10010];
  7. bool visited[10010];
  8. string s;
  9.  
  10. map<char, string> Map;
  11.  
  12. void insert(string s1){
  13. 	int index, node = 0;
  14. 	string temp;
  15. 	for(int i=0 ; s1[i] ; i++){
  16. 		for(int j=0 ; Map[s1[i]][j] ; j++){
  17. 			if(Map[s1[i]][j] == '.')
  18. 				index = 0;
  19. 			else 
  20. 				index = 1;
  21. 			if(trie[node][index] == -1){
  22. 				trie[node][index] = k++;
  23. 			}
  24. 			node = trie[node][index];
  25. 		}
  26. 	}
  27.  
  28. 	if(trie[node][2] == -1)
  29. 		trie[node][2] = 1;
  30. 	else
  31. 		trie[node][2]++; 
  32. }
  33.  
  34. void search(int i, int len, int node, int last){
  35. 	int index;
  36. 	if(i == len){
  37. 		if(trie[node][2] != -1)
  38. 			dp[last] += trie[node][2];
  39. 		return;
  40. 	}
  41.  
  42. 	if(s[i] == '.')
  43. 		index = 0;
  44. 	else 
  45. 		index = 1;
  46.  
  47. 	if(trie[node][2] != -1){
  48. 		if(!visited[i]){
  49. 			visited[i] = true;
  50. 			if(trie[0][index] != -1){
  51. 				search(i+1, len, trie[0][index], i);
  52. 				dp[last] += dp[i];
  53. 			}
  54. 		} else {
  55. 			dp[last] += dp[i];
  56. 		}
  57. 	}
  58.  
  59. 	if(trie[node][index] != -1){
  60. 		search(i+1, len, trie[node][index], last);
  61. 	}
  62. }
  63.  
  64. void initMap(){
  65. 	Map['A'] = ".-", Map['B'] = "-...", Map['C'] = "-.-.", Map['D'] = "-.."; 
  66. 	Map['E'] = "." , Map['F'] = "..-.", Map['G'] = "--.", Map['H'] = "...."; 
  67. 	Map['I'] = "..", Map['J'] = ".---", Map['K'] = "-.-", Map['L'] = ".-.."; 
  68. 	Map['M'] = "--", Map['N'] = "-.", Map['O'] = "---", Map['P'] = ".--."; 
  69. 	Map['Q'] = "--.-", Map['R'] = ".-.", Map['S'] = "...", Map['T'] = "-"; 
  70. 	Map['U'] = "..-", Map['V'] = "...-", Map['W'] = ".--", Map['X'] = "-..-"; 
  71. 	Map['Y'] = "-.--", Map['Z'] = "--..";
  72. }
  73.  
  74. int main(){
  75. 	int t;
  76. 	cin>>t;
  77.  
  78. 	initMap();
  79.  
  80. 	while(t--){
  81. 		string s1;
  82. 		cin>>s;
  83. 		k = 1;
  84. 		int l = s.length();
  85.  
  86. 		memset(trie, -1, sizeof(trie));
  87. 		memset(dp, 0, sizeof(dp));
  88.  
  89. 		int n;
  90. 		cin>>n;
  91.  
  92. 		for(int i=0 ; i<n ; i++){
  93. 			cin>>s1;
  94. 			insert(s1);
  95. 		}
  96.  
  97. 		search(0, l, 0, 0);
  98.  
  99. 		cout<<dp[0]<<endl;
  100. 	}
  101.  
  102. 	return 0;
  103. }
Success #stdin #stdout 0s 12712KB
comments (?)
stdin
copy 
1 
.---.--.-.-.-.---...-.---. 
6 
AT 
TACK 
TICK 
ATTACK 
DAWN 
ATTACK
stdout
copy 
2
https://ideone.com/qmIMKm
language:
C++ (gcc 8.3)
created:
9 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!