#include <string>
#include <vector>
#include <memory>
#include <cstring>
#include <iostream>

template<size_t K>
struct vertex
{
        int next[K];    // index to the next vertex by char
        bool leaf;      // is terminal
        int p;          // parent vertex
        char pch;       // parent char which leads to this vertex
        int link;       // suffix link
        int go[K];      // automaton goto function
        int out;        // suffix link to leaf
        int key_idx;    // index of key
};


template<size_t K = 26, size_t NMAX = 500>
class automaton
{
public:
        automaton()
        {
                t[0].p = t[0].link = -1;
                memset(t[0].next, 255, sizeof t[0].next);
                memset(t[0].go, 255, sizeof t[0].go);
                sz = 1;
        }

        void add_string (const std::string& s) {
                int v = 0;
                for (size_t i = 0; i < s.length(); ++i)
                {
                        char c = s[i]-'a';
                        if (t[v].next[c] == -1) {
                                memset (t[sz].next, 255, sizeof t[sz].next);
                                memset (t[sz].go, 255, sizeof t[sz].go);
                                t[sz].link = -1;
                                t[sz].p = v;
                                t[sz].pch = c;
                                t[sz].leaf = false;
                                t[sz].out = -1;
                                t[v].next[c] = sz++;
                        }
                        v = t[v].next[c];
                }
                t[v].leaf = true;

                keys.push_back(s);
                t[v].key_idx = keys.size() - 1;
        }

        int get_link(int v) {
                if (t[v].link == -1)
                        if (v == 0 || t[v].p == 0)
                                t[v].link = 0;
                        else
                                t[v].link = go(get_link(t[v].p), t[v].pch);
                return t[v].link;
        }

        int go(int v, char c) {
                if(t[v].go[c] == -1)
                        if(t[v].next[c] != -1)
                                t[v].go[c] = t[v].next[c];
                        else
                                t[v].go[c] = v==0 ? 0 : go(get_link(v), c);
                return t[v].go[c];
        }

        int out(int v)
        {
                if(t[v].out == -1)
                {
                        int u = get_link(v);
                        if(t[u].leaf)
                                t[v].out = u;
                        else if(u == 0)
                                t[v].out = 0;
                        else
                                t[v].out = out(u);
                }

                return t[v].out;
        }

        void check(int v, int i)
        {
                for(int u = v; v != 0; v = out(v))
                {
                        if(t[u].leaf)
                        {
                                int k = t[u].key_idx;
                                std::cout << (i - keys[k].length() + 1)
                                          << " "
                                          << keys[k]
                                          << std::endl;
                        }
                }
        }

        void check2(int v, int i)
        {
                {
                        if(t[v].leaf)
                        {
                                int k = t[v].key_idx;
                                std::cout << (i - keys[k].length() + 1)
                                          << " "
                                          << keys[k]
                                          << std::endl;
                        }
                }
        }

        void find_all_occurrences(const std::string& text)
        {
                int v = 0;
                for(int i = 0; i < text.length(); ++i)
                {
                        v = go(v, text[i] - 'a');
                        check(v, i + 1);
                }
        }


private:
        vertex<K> t[NMAX+1];
        int sz;
        std::vector<std::string> keys;
};

//
//class Solution {
//public:
//        std::vector<std::string> wordBreak(std::string s,
//                                           std::vector<std::string>& wordDict) {
//
//
//        }
//};

void _test_1()
{
        std::vector<std::string> dict = {"apple", "pen", "applepen",
                                         "pine", "pineapple"};

        std::string s = "pineapplepenapple";


        automaton<> m;

        for(const auto& k : dict)
                m.add_string(k);

        m.find_all_occurrences(s);
}

void _test_2()
{
        std::vector<std::string> dict = {"abc", "bcdc", "cccb",
                                         "bcdd", "bbbc"};

        std::string s = "abcdcbcddbbbcccbbbcccbb";


        automaton<> m;

        for(const auto& k : dict)
                m.add_string(k);

        m.find_all_occurrences(s);
}

int main()
{
	std::cout<<"Test 1:"<<std::endl;
	_test_1();
	std::cout<<"Test 2:"<<std::endl;
	_test_2();
	
	return 0;
}