fork download
  1. //#ifdef ONLINE_JUDGE
  2. //#define NDEBUG
  3. //#endif
  4.  
  5. #include <cstdio>
  6. #include <cassert>
  7. #include <cstring>
  8. #include <cmath>
  9. #include <limits>
  10. #include <map>
  11. #include <queue>
  12. #include <algorithm>
  13.  
  14. #ifndef NDEBUG
  15. #include <string>
  16. #endif
  17.  
  18. #define MAX_S_LENGTH 100000
  19. #define MAX_T_LENGTH 1000
  20. #define MAX_K 10
  21. #define MAX_Q 1000
  22.  
  23. #define ALPHA ('Z' - 'A' + 1 + 'z' - 'a' + 1 + 1)
  24. #define ENCODE(c) (isupper((c)) ? c - 'A' + 1 : c ? 'Z' - 'A' + 1 + c - 'a' + 1 : 0)
  25.  
  26. class Ukkonen
  27. {
  28. class Edge
  29. {
  30. public:
  31. static const int INFTY = std::numeric_limits<int>::max();
  32.  
  33. protected:
  34. int begin; //inclusive
  35. int end; //exclusive
  36.  
  37. const Ukkonen *ukkonen;
  38.  
  39. Edge(int begin, int end, const Ukkonen *ukkonen) :
  40. begin(begin),
  41. end(end),
  42. ukkonen(ukkonen)
  43. {}
  44.  
  45. public:
  46. int &getBegin() {return begin;}
  47. int getBegin() const {return begin;}
  48. int getEnd() const {return INFTY == end ? ukkonen->length : end; }
  49. int getLength() const {return getEnd() - getBegin(); }
  50. };
  51.  
  52. struct Node : public Edge
  53. {
  54. Node *parent;
  55. Node *link;
  56.  
  57. Node *children[ALPHA];
  58.  
  59. Node(int begin, int end, const Ukkonen *ukkonen):
  60. Edge(begin, end, ukkonen),
  61. parent(NULL),
  62. link(NULL)
  63. {memset(children, NULL, sizeof(children));};
  64.  
  65. ~Node()
  66. {
  67. for (const auto &child : children)
  68. {
  69. delete child;
  70. }
  71. }
  72. };
  73.  
  74. struct State
  75. {
  76. Node *node;
  77. int position; // on edge which enters node
  78.  
  79. State(Node *node, int position) : node(node), position(position) {}
  80. };
  81.  
  82. int go(State &state, const char needle[], int begin, int end)
  83. {
  84. while (begin < end)
  85. {
  86. assert(state.position <= state.node->getLength());
  87.  
  88. if (state.node->getLength() == state.position)
  89. {
  90. if (state.node->children[needle[begin]])
  91. {
  92. state.node = state.node->children[needle[begin]];
  93. state.position = 0;
  94. }
  95. else
  96. {
  97. break;
  98. }
  99. }
  100. else if (needle[begin] == buffer[state.node->getBegin() + state.position])
  101. {
  102. ++begin;
  103. ++state.position;
  104. }
  105. else
  106. {
  107. break;
  108. }
  109. }
  110.  
  111. return end - begin;
  112. }
  113.  
  114. Node *split(const State &state)
  115. {
  116. Node *separator;
  117.  
  118. assert(0 <= state.position && state.position <= state.node->getLength());
  119.  
  120. if (state.node->getLength() == state.position)
  121. {
  122. separator = state.node;
  123. }
  124. else if (0 == state.position)
  125. {
  126. separator = state.node->parent;
  127. }
  128. else
  129. {
  130. separator = new Node(state.node->getBegin(), state.node->getBegin() + state.position, this);
  131. separator->parent = state.node->parent;
  132. separator->children[buffer[state.node->getBegin() + state.position]] = state.node;
  133.  
  134. assert(0 == state.node->getLength() || state.node->parent->children[buffer[state.node->getBegin()]] == state.node);
  135. state.node->parent->children[buffer[state.node->getBegin()]] = separator;
  136.  
  137. state.node->getBegin() = state.node->getBegin() + state.position;
  138. state.node->parent = separator;
  139. }
  140.  
  141.  
  142. setLink(nodeWithoutLink, separator);
  143. nodeWithoutLink = separator;
  144.  
  145. return separator;
  146. }
  147.  
  148. void extend(int position)
  149. {
  150. assert(position == length);
  151. ++length;
  152. nodeWithoutLink = &dummyNode;
  153.  
  154. while(true)
  155. {
  156. State copy = state;
  157. int left = go(state, buffer, position, position + 1);
  158.  
  159. if (0 == left)
  160. {
  161. assert(0 != memcmp(&copy, &state, sizeof(State)));
  162.  
  163. if (copy.position == copy.node->getLength())
  164. {
  165. setLink(nodeWithoutLink, copy.node);
  166. }
  167.  
  168. nodeWithoutLink = &dummyNode;
  169.  
  170. break;
  171. }
  172.  
  173. assert(left == 1);
  174. assert(0 == memcmp(&state, &copy, sizeof(State)));
  175.  
  176. Node *separator = split(state);
  177. Node *leaf = new Node(position, Edge::INFTY, this);
  178.  
  179. // assert(root == separator || 0 < separator->children.size());
  180. assert(0 == separator->children[buffer[position]]);
  181. separator->children[buffer[position]] = leaf;
  182. leaf->parent = separator;
  183.  
  184. state.node = separator->parent->link;
  185. state.position = separator->parent->link->getLength();
  186.  
  187. int zero = go(state, buffer, separator->getBegin() + (root == separator->parent), separator->getEnd());
  188. assert(0 >= zero);
  189.  
  190. if (root == leaf->parent)
  191. {
  192. break;
  193. }
  194. }
  195.  
  196. setLink(nodeWithoutLink, root);
  197. }
  198.  
  199. void setLink(Node *node, Node *suffixNode)
  200. {
  201. assert(&dummyNode == node || NULL == node->link || suffixNode == node->link);
  202. node->link = suffixNode;
  203. assert(root == nodeWithoutLink || &dummyNode == nodeWithoutLink || getString(node).substr(1) == getString(suffixNode));
  204. }
  205.  
  206. #ifndef NDEBUG
  207. std::string getString(Node *vertex)
  208. {
  209. std::string result = "";
  210.  
  211. while (root != vertex)
  212. {
  213. for (int i = vertex->getEnd() - 1; i >= vertex->getBegin(); --i)
  214. {
  215. result += buffer[i];
  216. }
  217.  
  218. vertex = vertex->parent;
  219. }
  220.  
  221. std::reverse(result.begin(), result.end());
  222.  
  223. return result;
  224. }
  225. #endif
  226.  
  227. public:
  228. Ukkonen(const char input[]):
  229. buffer(new char[strlen(input) + 1]),
  230. root(new Node(0, 0, this)),
  231. state(root, 0),
  232. nodeWithoutLink(NULL),
  233. dummyNode(-1, -1, this),
  234. length(0)
  235. {
  236. int i;
  237.  
  238. for (i = 0; input[i]; ++i)
  239. {
  240. buffer[i] = ENCODE(input[i]);
  241. }
  242.  
  243. buffer[i] = ENCODE('\0');
  244.  
  245. int position;
  246.  
  247. root->parent = root;
  248. root->link = root;
  249.  
  250. nodeWithoutLink = &dummyNode;
  251.  
  252. for (position = 0; buffer[position]; ++position)
  253. {
  254. extend(position);
  255. }
  256.  
  257. extend(position);
  258. }
  259.  
  260. ~Ukkonen()
  261. {
  262. delete [] buffer;
  263. delete root;
  264. }
  265.  
  266. bool isSubstring(const char substring[])
  267. {
  268. static char encodedSubstring[MAX_T_LENGTH + 1];
  269. int length = (int)strlen(substring);
  270. State state(root, 0);
  271.  
  272. for (int i = 0; i <= length; ++i)
  273. {
  274. encodedSubstring[i] = ENCODE(substring[i]);
  275. }
  276.  
  277. int left = go(state, encodedSubstring, 0, length);
  278. assert(0 <= left);
  279. return 0 == left;
  280. }
  281.  
  282. private:
  283. char *buffer;
  284. Node *root;
  285. Node *nodeWithoutLink;
  286. State state;
  287. Node dummyNode;
  288. int length;
  289. };
  290.  
  291. template <class Callback>
  292. void iterateOverStrings(int lengthBegin, int lengthEnd, Callback callback)
  293. {
  294. assert(lengthBegin <= lengthEnd);
  295. const int alpha = 'z' - 'a' + 1;
  296. const unsigned long long beginMask = 0;
  297. unsigned long long endMask = 1;
  298.  
  299. for (int length = 0; length < lengthEnd; ++length)
  300. {
  301. if (lengthBegin <= length)
  302. {
  303. char buffer[length + 1];
  304.  
  305. for (unsigned long long mask = beginMask; mask < endMask; ++mask)
  306. {
  307. unsigned long long maskCopy = mask;
  308.  
  309. for (int index = 0; index < length; ++index)
  310. {
  311. buffer[index] = maskCopy % alpha + 'a';
  312. maskCopy /= alpha;
  313. }
  314.  
  315. assert(0 == maskCopy);
  316. buffer[length] = '\0';
  317.  
  318. callback(buffer);
  319. }
  320. }
  321.  
  322. endMask *= alpha;
  323. }
  324. }
  325.  
  326. void uva_10679()
  327. {
  328. int k;
  329.  
  330. scanf("%d", &k);
  331. for (int testcase = 0; testcase < k; ++testcase)
  332. {
  333. static char s[MAX_S_LENGTH + 1];
  334. int q;
  335.  
  336. scanf(" %s%d", s, &q);
  337.  
  338. Ukkonen ukkonen(s);
  339.  
  340. for (int query = 0; query < q; ++query)
  341. {
  342. static char t[MAX_T_LENGTH + 1];
  343.  
  344. scanf(" %s", t);
  345.  
  346. if (ukkonen.isSubstring(t))
  347. {
  348. printf("y\n");
  349. }
  350. else
  351. {
  352. printf("n\n");
  353. }
  354. }
  355. }
  356. }
  357.  
  358. void unitTest()
  359. {
  360. assert(0 == ENCODE('\0'));
  361. assert(1 == ENCODE('A'));
  362. assert(26 == ENCODE('Z'));
  363. assert(27 == ENCODE('a'));
  364. assert(52 == ENCODE('z'));
  365.  
  366. srand(42);
  367.  
  368. {
  369. Ukkonen ukkonen("bbaabbbab");
  370. assert(ukkonen.isSubstring("bab"));
  371. }
  372. {
  373. Ukkonen ukkonen("abbaabbbabaaaabbabbaabbaaaaabaaabbaaaabbbbbabbbbaabbbabaaaaaaaaaaaaaabbaabababaabbbbbbbbbbbbbbbbaba");
  374. assert(ukkonen.isSubstring("bab"));
  375. }
  376. {
  377. Ukkonen ukkonen("ababc");
  378. assert(ukkonen.isSubstring("bc"));
  379. }
  380. {
  381. Ukkonen ukkonen("mfkfkhgv");
  382. assert(ukkonen.isSubstring("kh"));
  383. }
  384. {
  385. Ukkonen ukkonen("bba");
  386. assert(ukkonen.isSubstring("ba"));
  387. }
  388. {
  389. Ukkonen ukkonen("a");
  390. assert(ukkonen.isSubstring(""));
  391. assert(ukkonen.isSubstring("a"));
  392. assert(!ukkonen.isSubstring("b"));
  393. assert(!ukkonen.isSubstring("aa"));
  394. }
  395. {
  396. Ukkonen ukkonen("aa");
  397. assert(ukkonen.isSubstring(""));
  398. assert(ukkonen.isSubstring("a"));
  399. assert(ukkonen.isSubstring("aa"));
  400. assert(!ukkonen.isSubstring("b"));
  401. }
  402. {
  403. Ukkonen ukkonen("ab");
  404. assert(ukkonen.isSubstring(""));
  405. assert(ukkonen.isSubstring("a"));
  406. assert(ukkonen.isSubstring("b"));
  407. assert(!ukkonen.isSubstring("aa"));
  408. assert(!ukkonen.isSubstring("ba"));
  409. }
  410. {
  411. Ukkonen ukkonen("");
  412. assert(ukkonen.isSubstring(""));
  413. assert(!ukkonen.isSubstring("a"));
  414. }
  415.  
  416. struct CheckCallback
  417. {
  418. Ukkonen &ukkonen;
  419. const char *string;
  420.  
  421. void operator()(const char substring[]) const
  422. {
  423. bool isSubstringAnswer = NULL != strstr(string, substring);
  424. bool isSubstringOutput = ukkonen.isSubstring(substring);
  425.  
  426. fprintf(stderr, "Is \"%s\" substring of \"%s\"?\n\tUkkonen: %d\n\tCorrect answer: %d\n", substring, string, isSubstringOutput, isSubstringAnswer);
  427.  
  428. assert(isSubstringAnswer == isSubstringOutput);
  429. }
  430.  
  431. CheckCallback(Ukkonen &ukkonen, const char string[]) : ukkonen(ukkonen), string(string){}
  432. };
  433.  
  434. {
  435. while (true)
  436. {
  437. enum
  438. {
  439. STRING,
  440. SUBSTRING,
  441. NUMBER
  442. };
  443.  
  444. int length[NUMBER];
  445. char *string[NUMBER];
  446.  
  447. for (int i = 0; i < NUMBER; ++i)
  448. {
  449. length[i] = rand() % 10;
  450. string[i] = new char[length[i] + 1];
  451.  
  452. for (int j = 0; j < length[i]; ++j)
  453. {
  454. string[i][j] = (char)(rand() % ('z' - 'a' + 1) + 'a');
  455. }
  456.  
  457. string[i][length[i]] = '\0';
  458. }
  459.  
  460. Ukkonen ukkonen(string[STRING]);
  461.  
  462. CheckCallback check(ukkonen, string[STRING]);
  463.  
  464. check(string[SUBSTRING]);
  465.  
  466. for (int i = 0; i < NUMBER; ++i)
  467. {
  468. delete [] string[i];
  469. }
  470. }
  471. }
  472.  
  473. {
  474. struct TestCallback
  475. {
  476. void operator()(const char buffer[]) const
  477. {
  478. Ukkonen ukkonen(buffer);
  479.  
  480. iterateOverStrings(0, (int)strlen(buffer) + 1, CheckCallback(ukkonen, buffer));
  481. }
  482. };
  483.  
  484. iterateOverStrings(0, 3, TestCallback());
  485. }
  486.  
  487.  
  488.  
  489. assert(true);
  490. }
  491.  
  492. void profileTestCreate()
  493. {
  494. freopen("input.txt", "w", stdout);
  495.  
  496. int k = MAX_K;
  497.  
  498. printf("%d\n", k);
  499.  
  500. for (int testcase = 0; testcase < k; ++testcase)
  501. {
  502. static char s[MAX_S_LENGTH + 1];
  503.  
  504. for (int i = 0; i < MAX_S_LENGTH; ++i)
  505. {
  506. s[i] = (rand() & 1 ? 'a' : 'A') + rand() % ('Z' - 'A' + 1);
  507. }
  508.  
  509. s[MAX_S_LENGTH] = '\0';
  510.  
  511. int q = MAX_Q;
  512.  
  513. printf("%s\n%d\n", s, q);
  514.  
  515. for (int query = 0; query < q; ++query)
  516. {
  517. static char t[MAX_T_LENGTH + 1];
  518.  
  519. for (int i = 0; i < MAX_T_LENGTH; ++i)
  520. {
  521. t[i] = (rand() & 1 ? 'a' : 'A') + rand() % ('Z' - 'A' + 1);
  522. }
  523.  
  524. t[MAX_T_LENGTH] = '\0';
  525.  
  526. printf("%s\n", t);
  527. }
  528. }
  529.  
  530. fflush(stdout);
  531. }
  532.  
  533. void profileTestRun()
  534. {
  535. freopen("input.txt", "r", stdin);
  536. freopen("output.txt", "w", stdout);
  537.  
  538. uva_10679();
  539. }
  540.  
  541. int main()
  542. {
  543. //unitTest();
  544. //profileTestCreate();
  545. //profileTestRun();
  546. uva_10679();
  547.  
  548.  
  549. return 0;
  550. }
  551.  
Success #stdin #stdout 0s 16288KB
stdin
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
stdout
y
n
y