zoj 3784 String of Infinity

zoj 3784 String of Infinity

#pragma warning(disable:4996)#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <set>#include <vector>#include<queue>#include<stack>#include <cmath>using namespace std;#define maxn 210000#define ll long longint n, m;struct Trie{    Trie *fail, *go[26];    bool ter; bool flag;    void init(){        memset(go, 0, sizeof(go)); fail = NULL; ter = false; flag = false;    }}pool[maxn], *root;int tot;void insert(char *c){    int len = strlen(c); Trie *p = root;    for (int i = 0; i < len; i++){        if (p->go[c[i] - 'a'] != 0) p = p->go[c[i] - 'a'];        else{ pool[tot].init(); p->go[c[i] - 'a'] = &pool[tot++]; p = p->go[c[i] - 'a'];        }    }    p->ter = true;}void getFail(){    queue<Trie*> que;    que.push(root);    root->fail = NULL;    while (!que.empty()){        Trie *temp = que.front(); que.pop();        Trie *p = NULL;        for (int i = 0; i < m; i++){ if (temp->go[i] != NULL){     if (temp == root) temp->go[i]->fail = root;     else{         p = temp->fail;         while (p != NULL){  if (p->go[i] != NULL){      temp->go[i]->fail = p->go[i]; break;  }  p = p->fail;         }         if (p == NULL) temp->go[i]->fail = root;     }     que.push(temp->go[i]); }        }    }}bool ddfs(Trie *p){    if (p == root||p==NULL) return false;    if (p->flag == true) return p->ter;    p->ter |= ddfs(p->fail); p->flag = true;    return p->ter;}int pre[maxn], low[maxn], sccno[maxn],siz[maxn];int sta[maxn],st;int dfs_clock;int scc_cnt;int siz2[maxn];void dfs(int u){    low[u] = pre[u] = ++dfs_clock;    sta[++st] = u;    for (int i = 0; i < m; i++){        Trie *p = pool[u].go[i];        if (p->ter) continue;        int v = p - pool;        if (!pre[v]){ dfs(v); low[u] = min(low[u], low[v]);        }        else if (!sccno[v]){ low[u] = min(low[u], pre[v]);        }    }    if (low[u] == pre[u]){        ++scc_cnt;        while (1){ int x = sta[st--]; sccno[x] = scc_cnt; siz[scc_cnt]++; if (x == u) break;        }    }}void find_scc(){    memset(siz, 0, sizeof(siz));    memset(sccno, 0, sizeof(sccno));    memset(low, 0, sizeof(low));    memset(pre, 0, sizeof(pre));    st = dfs_clock = 0; scc_cnt = 0;    for (int i = 0; i < tot; i++){        if (pool[i].ter) continue;        if (!pre[i]) dfs(i);    }}char str[1500];int main(){    int T; cin >> T;    while (T--)    {        cin >> n >> m;        tot = 0; root = &pool[tot++]; root->init();        for (int i = 0; i < n; i++){ scanf("%s", str); insert(str);        }        getFail();        for (int i = 0; i < tot; i++) ddfs(&pool[i]);        for (int i = 0; i < tot; i++){ Trie *p = &pool[i]; for (int k = 0; k < m; k++){     if (p->go[k] == NULL){         Trie *temp = p; temp = temp->fail;         while (temp != NULL){  if (temp->go[k] != NULL) {      p->go[k] = temp->go[k]; break;  }  temp = temp->fail;         }         if (temp == NULL) p->go[k] = root;     } }        }        find_scc();        memset(siz2, 0, sizeof(siz2));        for (int i = 0; i < tot; i++){ if (pool[i].ter) continue; for (int j = 0; j < m; j++){     int k = pool[i].go[j] - pool;     if (sccno[k] == sccno[i]){         siz2[sccno[k]]++;     } }        }        bool flag = false;        for (int i = 1; i <= scc_cnt; i++){ if (siz2[i]>siz[i]){     flag = true; break; }        }        if (flag) puts("Yes");        else puts("No");    }    return 0;}