AC自动机简单题(三)

2013-07-23 09:07:18 · 作者: · 浏览: 546


    //  while(u && !c[u][k]) u = f[u]; // 改造后的AC自动机,这句话不用写
    u = c[u][k];
    for(j = u; j; j = f[j]) {
    for(int k = 0; k < id[j].size(); k++)
    cnt[id[j][k]]++;
    }
    }
    }
    }ac;
    int main() {
    int i, j;
    while( ~scanf("%d", &n) && n) {
    ac.init();
    memset(cnt, 0, sizeof(cnt));
    for(i = 1; i <= n; i++) {

    scanf("%s", str[i]);
    ac.insert(str[i], i);
    }
    ac.getfail();
    scanf("%s", s);
    ac.find(s);
    int ans = 0;
    for(i = 1; i <= n; i++)
    if(ans < cnt[i]) ans = cnt[i];
    printf("%d\n", ans);
    for(i = 1; i <= n; i++)
    if(ans == cnt[i]) puts(str[i]);
    }
    return 0;
    }