fork download
  1. //
  2. // 10679-i-love-strings.cpp
  3. // 10679-I-Love-Strings
  4. //
  5. // Created by Volodymyr Polosukhin on 10/10/2017.
  6. // Copyright © 2017 Volodymyr Polosukhin. All rights reserved.
  7. //
  8.  
  9. #define NDEBUG
  10.  
  11. #include <cstdio>
  12. #include <cassert>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <limits>
  16.  
  17. #define INFTY (std::numeric_limits<int>::max())
  18. #define CHARACTERS_NUMBER (('z' - 'a' + 1) + ('Z' - 'A' + 1) + 1)
  19. #define ILLEGAL_INDEX (0)
  20. #define MAX_S_LENGTH (100000)
  21. #define MAX_T_LENGTH (1000)
  22.  
  23. int length;
  24. int nodesSize;
  25.  
  26. struct Node
  27. {
  28. int begin;
  29. int end;
  30.  
  31. int parent;
  32. int link;
  33. int characterToNode[CHARACTERS_NUMBER];
  34.  
  35. int getBegin() const { return begin; }
  36. int getEnd() const { return INFTY == end ? length : end; }
  37. int getLength() const { return getEnd() - getBegin(); }
  38. };
  39.  
  40. char buffer[MAX_S_LENGTH + 1];
  41. Node nodes[MAX_S_LENGTH + 2];
  42.  
  43. int dummy;
  44. int root;
  45.  
  46. int currentPosition;
  47. int currentNode;
  48.  
  49. inline int go(int &currentNode, int &currentPosition, const char needle[], int begin, int end)
  50. {
  51. while (begin < end)
  52. {
  53. assert(currentNode < nodesSize);
  54.  
  55. assert(currentPosition <= nodes[currentNode].getLength());
  56.  
  57. if (nodes[currentNode].getLength() == currentPosition)
  58. {
  59. if (ILLEGAL_INDEX == nodes[currentNode].characterToNode[needle[begin]])
  60. {
  61. break;
  62. }
  63.  
  64. currentNode = nodes[currentNode].characterToNode[needle[begin]];
  65. currentPosition = 0;
  66. }
  67. else if (needle[begin] == buffer[nodes[currentNode].begin + currentPosition])
  68. {
  69. ++begin;
  70. ++currentPosition;
  71. }
  72. else
  73. {
  74. break;
  75. }
  76. }
  77.  
  78. return begin < end ? end - begin : 0;
  79. }
  80.  
  81. inline void extend(char character)
  82. {
  83. buffer[length++] = character;
  84. int nodeWithoutLink = dummy;
  85.  
  86. while (true)
  87. {
  88. int previousPosition = currentPosition;
  89. int previousNode = currentNode;
  90.  
  91. int left = go(currentNode, currentPosition, buffer, length - 1, length);
  92.  
  93. if (0 == left)
  94. {
  95. if (previousPosition == nodes[previousNode].getLength())
  96. {
  97. nodes[nodeWithoutLink].link = previousNode;
  98. nodeWithoutLink = dummy;
  99. }
  100.  
  101. break;
  102. }
  103.  
  104. assert(1 == left);
  105. assert(previousNode == currentNode);
  106. assert(previousPosition == currentPosition);
  107. assert(0 <= currentPosition && currentPosition <= nodes[currentNode].getLength());
  108.  
  109. int separator;
  110.  
  111. if (nodes[currentNode].getLength() == currentPosition)
  112. {
  113. separator = currentNode;
  114. }
  115. else if (0 == currentPosition)
  116. {
  117. separator = nodes[currentNode].parent;
  118. }
  119. else
  120. {
  121. separator = nodesSize++;
  122.  
  123. nodes[separator].begin = nodes[currentNode].getBegin();
  124. nodes[separator].end = nodes[currentNode].getBegin() + currentPosition;
  125. nodes[separator].parent = nodes[currentNode].parent;
  126. nodes[separator].characterToNode[buffer[nodes[currentNode].getBegin() + currentPosition]] = currentNode;
  127.  
  128. assert(0 == nodes[currentNode].getLength() || nodes[nodes[currentNode].parent].characterToNode[buffer[nodes[currentNode].getBegin()]] == currentNode);
  129.  
  130. nodes[nodes[currentNode].parent].characterToNode[buffer[nodes[currentNode].getBegin()]] = separator;
  131.  
  132. nodes[currentNode].begin += currentPosition;
  133. nodes[currentNode].parent = separator;
  134.  
  135. assert(nodes[currentNode].begin <= nodes[currentNode].end);
  136. }
  137.  
  138. nodes[nodeWithoutLink].link = separator;
  139. nodeWithoutLink = separator;
  140.  
  141. int leaf = nodesSize++;
  142.  
  143. assert(ILLEGAL_INDEX == nodes[separator].characterToNode[character]);
  144. nodes[separator].characterToNode[character] = leaf;
  145. nodes[leaf].begin = length - 1;
  146. nodes[leaf].end = INFTY;
  147. nodes[leaf].parent = separator;
  148.  
  149. currentNode = nodes[nodes[separator].parent].link;
  150. currentPosition = nodes[currentNode].getLength();
  151. assert(ILLEGAL_INDEX != currentNode);
  152. int zero = go(currentNode, currentPosition, buffer, nodes[separator].getBegin() + (root == nodes[separator].parent), nodes[separator].getEnd());
  153. assert(0 >= zero);
  154.  
  155. if (root == separator)
  156. {
  157. break;
  158. }
  159.  
  160. nodes[nodeWithoutLink].link = root;
  161. }
  162. }
  163.  
  164. inline void init()
  165. {
  166. length = 0;
  167. nodesSize = 2;
  168. dummy = ILLEGAL_INDEX;
  169. root = 1;
  170. currentPosition = 0;
  171. currentNode = root;
  172. memset(nodes, 0, sizeof(nodes));
  173. nodes[root].begin = nodes[root].end = 0;
  174. nodes[root].parent = nodes[root].link = root;
  175. }
  176.  
  177. inline void ukkonen(const char buffer[])
  178. {
  179. init();
  180.  
  181. for (const char *pointer = buffer; *pointer; ++pointer)
  182. {
  183. extend(*pointer);
  184. }
  185.  
  186. extend('\0');
  187. }
  188.  
  189. inline bool isSubstring(int length, const char needle[])
  190. {
  191. int currentNode = root;
  192. int currentPosition = 0;
  193.  
  194. int left = go(currentNode, currentPosition, needle, 0, length);
  195. assert(0 <= left);
  196.  
  197. return 0 == left;
  198. }
  199.  
  200. void encodeString(char string[])
  201. {
  202. for (char *pointer = string; *pointer; ++pointer)
  203. {
  204. if (isupper(*pointer))
  205. {
  206. *pointer = (*pointer - 'A') + 1;
  207. }
  208. else
  209. {
  210. assert(islower(*pointer));
  211. *pointer = (*pointer - 'a') + ('Z' - 'A' + 1) + 1;
  212. }
  213. }
  214. }
  215.  
  216. void uva_10679()
  217. {
  218. int k;
  219.  
  220. scanf("%d", &k);
  221.  
  222. for (int testcase = 0; testcase < k; ++testcase)
  223. {
  224. static char s[MAX_S_LENGTH + 1];
  225. int q;
  226.  
  227. scanf(" %s%d", s, &q);
  228.  
  229. encodeString(s);
  230.  
  231. ukkonen(s);
  232.  
  233. for (int query = 0; query < q; ++query)
  234. {
  235. static char t[MAX_T_LENGTH + 1];
  236.  
  237. scanf(" %s", t);
  238.  
  239. encodeString(t);
  240.  
  241. if (isSubstring(strlen(t), t))
  242. {
  243. printf("y\n");
  244. }
  245. else
  246. {
  247. printf("n\n");
  248. }
  249. }
  250. }
  251. }
  252.  
  253. void unit_test()
  254. {
  255. {
  256. char s[] = "abcdefghABCDEFGH";
  257. encodeString(s);
  258. ukkonen(s);
  259. {
  260. char t[] = "abc";
  261. encodeString(t);
  262. assert(true == isSubstring(3, t));
  263. }
  264. {
  265. char t[] = "abAB";
  266. encodeString(t);
  267. assert(false == isSubstring(4, t));
  268. }
  269. }
  270. {
  271. char s[] = "xyz";
  272. encodeString(s);
  273. ukkonen(s);
  274. char t[] = "xyz";
  275. encodeString(t);
  276. assert(true == isSubstring(3, t));
  277. }
  278. }
  279.  
  280. int main()
  281. {
  282. //unit_test();
  283. uva_10679();
  284.  
  285. return 0;
  286. }
  287.  
Success #stdin #stdout 0s 38528KB
stdin
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
stdout
y
n
y