fork download
copy 
  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
comments (?)
stdin
copy 
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
stdout
copy 
y
n
y
https://ideone.com/umNKBV
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!