fork download
copy 
  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
comments (?)
stdin
copy 
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
stdout
copy 
y
n
y
https://ideone.com/mVP6Px
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!