C++, using trie tree and manacher , O(N * K)


  • -1
    L
    struct Node
    {
        int link[26];
        int tail;
        void init()
        {
            memset(link, -1, sizeof(link));
            tail = -1;
        }
    }
    // tr[100009]
    ;
    
    // int id;
    
    vector<Node> tr;
    class Solution {
    public:
        
        void insert(const string &s, int _id)
        {
            int n = s.size();
            int top = 0;
            for(int i = 0; i < n; ++ i)
            {
                int ch = s[i] - 'a';
                if(tr[top].link[ch] == -1)
                {
                    // tr[top].link[ch] = id;
                    // tr[id ++].init();
                    tr[top].link[ch] = tr.size();
                    tr.push_back(Node());
                    tr.back().init();
                }
                top = tr[top].link[ch];
            }
            tr[top].tail = _id;
        }
    
        
        vector<int> p;
        // const string *cntS;
        void setCntS(const string &r)
        {
            // cntS = &r;
            
            // return ;
            
            int n = r.size() * 2 + 1;
            
            auto s = [&](int i) ->int {
                if(i & 1) return r[i >> 1];
                return '#';
            };
            
            p[0] = 0;
            int id = 0;
            for(int i = 1; i < n; ++ i)
            {
                if(2 * id - i >= 0)
                {
                    p[i] = min(p[2 * id - i], id + p[id] - i);
                }
                else 
                {
                    p[i] = 0;
                }
                while(1)
                {
                    int R = i + p[i] + 1, L = i - p[i] - 1;
                    if(L >= 0 && R < n && s(L) == s(R))
                        p[i] ++;
                    else break;
                }
                if(id + p[id] < i + p[i]) id = i;
            }
            
        }
        bool isP(int i, int j)
        {
            
            // while(i < j) 
            // {
            //     if((*cntS)[i] == (*cntS)[j]) i ++, j --;
            //     else return 0;
            // }
            // return 1;
            
            int mid = i + j + 1;
            
            int L = mid - p[mid], R = mid + p[mid];
            return 2 * i + 1 >= L && 2 * j + 1<= R;
        }
        
        
        
        
        vector<vector<int> > ans;
        void query(const string &s, int now_id, bool sec)
        {
            
            setCntS(s);
            int n = s.size();
                
            int top = 0;
            for(int j = 0; j < s.size(); ++ j)
            {
                int ch = s[j] - 'a';
                if(tr[top].link[ch] != -1)
                {
                    top = tr[top].link[ch];
                    if(tr[top].tail != -1 && tr[top].tail != now_id)
                    {
                        if(isP(j + 1, n - 1))
                        {
                            if(!sec)
                                ans.push_back({now_id, tr[top].tail }) ;
                            else if(j != n - 1) 
                            {
                                ans.push_back({tr[top].tail,now_id }) ;
                            }
                                
                        }
                    }
                }
                else break;
            }
        }
        vector<vector<int>> palindromePairs(vector<string>& ws)
        {
            
            ans.clear();
            p.resize(10000);
            
            
            // id = 1;
            // tr[0].init();
            tr.clear();
            tr.push_back(Node());
            tr.back().init();
            for(int i = 0; i < ws.size(); ++ i)
            {
                reverse(ws[i].begin(), ws[i].end());
                insert(ws[i], i);
                reverse(ws[i].begin(), ws[i].end());
            }
            for(int i = 0; i < ws.size(); ++ i)
            {
                query(ws[i], i, 0);
            }
            
            
            // id = 1;
            // tr[0].init();
            tr.clear();
            tr.push_back(Node());
            tr.back().init();
            
            for(int i = 0; i < ws.size(); ++ i)
            {
                insert(ws[i], i);
            }
            for(int i = 0; i < ws.size(); ++ i)
            {
                reverse(ws[i].begin(), ws[i].end());
                query(ws[i], i, 1);
            }
            
            
            vector<int> e, ne;
            for(int i = 0; i < ws.size(); ++ i)
            {
                if(ws[i].size() == 0) e.push_back(i);
                else ne.push_back(i);
            }
            
            for(int j = 0; j < ne.size(); ++ j)
            {
                int n = ws[ne[j]].size();
                
                setCntS(ws[ne[j]]);
                if(!isP(0, n - 1)) continue;
                
                for(int i = 0; i < e.size(); ++ i)
                {
                    ans.push_back({e[i], ne[j]});
                    ans.push_back({ne[j], e[i]});
                }
            }
            for(int i = 0; i < e.size(); ++ i)
            {
                for(int j = 0; j < e.size(); ++ j)
                {
                    if(i != j)
                    {
                        ans.push_back({e[i], e[j]});
                    }
                }
            }
            return ans;
            
            
            
        }
    };

  • 2

    Veeeeery long and obscure code.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.