• + 1 comment

    C++ solution

    #include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    
    using namespace std;
    
    #define MM 9000000
    
    char mark[20][100005];
    int L;
    const int inf =  0x3F3F3F3F;  
    typedef long long lint;
    char text[11][100005];
    int x[11], best[1<<20], covered[1<<20];
    int CC;
        
    typedef struct N{
        int llen;
        struct N *next[160];
        struct N *fail;
        N(){
            llen = -1;
            for(int i = 0; i < 160; i++) next[i] = NULL;
            fail = NULL;
        }
    } Node;
        
    Node *root;
    Node *queue[MM + 10];
    int front,rear;
    char command[MM + 10];
        
    inline int idd(char ch){
        return (int)ch;
    }
        
    void Insert(char *s){
        int L = strlen(s);
        Node *cur = root;
        for(int i = 0; i < L; i++){
            int t = idd(s[i]);
            if(cur->next[t] == NULL) cur = cur->next[t] = new Node();
            else cur = cur->next[t];
        }
        cur->llen = max(cur->llen, (int)strlen(s));
    }
        
    void AC_Make(){
        front=rear=0;
        queue[rear++]=root;
        while(rear>front){
            Node *cur=queue[front++];
            if(cur->fail!=NULL){
                cur->llen = max(cur->llen, cur->fail->llen);
            }
            for(int i = 0; i < 160; i++){
                if(cur->next[i] == NULL){
                    cur->next[i] = (cur == root) ? root : cur->fail->next[i];
                } else {
                    cur->next[i]->fail = (cur == root) ? root : cur->fail->next[i];
                    queue[rear++] = cur->next[i];
                }
            }
        }
    }
        
    // make st to en as 0 inclusive!
    void mz(int st, int en, int lev = 0, int ls = 0, int le = L - 1){
        if ( en < ls || st > le ) return;
        if (ls >= st && le <= en || ls == le){
            //mark this range as 0
            mark[lev][ls] = 0;
            return;
        }
        int mid = (ls + le) >> 1;
        if (mid >= ls) mz(st, en, lev + 1, ls, mid);
        if (mid + 1 <= le) mz(st, en, lev + 1, mid + 1, le);
    }
        
    bool isz(int id, int lev = 0, int ls = 0, int le = L - 1){
        if ( id < ls || id > le || le < ls) return true;
        if (ls == le) return mark[lev][ls];
        bool ans = mark[lev][ls];
        if(!ans) return ans;
        int mid = (ls + le) >> 1;
        if (mid >= ls && id <= mid) ans &= isz(id, lev + 1, ls, mid);
        else if (mid+1 <= le) ans &= isz(id, lev + 1, mid + 1, le);
        return ans;
    }
        
    // this will return the power of the current string!
    int query(char s[]){
        memset(mark, -1, sizeof mark);
        L = strlen(s);
        Node *cur = root;
        for(int i = 0; i < L; i++){
            cur=cur->next[idd(s[i])];
            if(cur->llen > 0){
                mz(i - cur->llen + 1, i);
            }
        }
        int ans = 0;
        for(int i = 0; i < L; i++){
            if (isz(i)){
                ans ++;
            }
        }
        return ans;
    }
        
    lint getHighestUngettable(int M){
        lint ret = -1;
        for(int i = 1; i < M; ++i) if(best[i] >= inf) return -1;
            else ret = max(ret, (best[i] - 1) * (lint)M + i);
        return ret;
    }
        
    void computeDistances2(int M, int n){
        for(int i = 0; i < M; ++i) best[i] = inf;
        best[0] = 0;    
        for(int j = 0; j < n; ++j){
            int c = x[j] / M, d = x[j] % M;
            if(d == 0) continue;
            ++CC;
            for(int start = 0; start < M; ++start) if(covered[start] != CC){
                int rep = 1 + (start > 0);
                while(rep--){
                    for(int l = (d + start) % M, prev = start;; prev = l,l = (l + d)){
                        if(l >= M) l -= M;
                        best[l] = min(best[l], c + best[prev] + (prev > l));
                        covered[l] = CC;
                        if(l == start) break;
                    }
                }
            }
        }
    }
        
    int main(){
        int m, n;
        scanf("%d\n", &n);
        for(int i = 0; i < n; i++){
            gets(text[i]);
            int l = strlen(text[i]);
            if(text[i][l - 1] == '\n') text[i][l - 1] = '\0';
        }
        root = new Node();
        scanf("%d\n", &m);
        for(int i = 0; i < m; i++){
            gets(command);
            int l = strlen(command);
            if(command[l - 1] == '\n')
                command[l - 1] = '\0';
            Insert(command);
        }
        AC_Make();
        for(int i = 0; i < n; i++) x[i] = query(text[i]);
        sort(x, x + n);
        n = unique(x, x + n) - x;
        swap(x[0], x[n - 1]);
        int M = x[n - 1];
        computeDistances2(M, n - 1);
        lint h = getHighestUngettable(M);
        printf("%lld\n", h);
        return 0;
    }