multi_line_cmp.cc

/**********************************************************************
Author: Sherlock
Created Time: 2008-10-28 16:24:47
File Name:
Description:
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

const int maxint = 0x7FFFFFFF;
const int maxSize = 100 + 10;
const int maxLen = 100 * 1100;

int n, m, len, num, total;
int fail[maxSize], que[maxSize], edge[maxSize][26];
char s[maxSize];
bool hash[maxSize];
long long f[30][maxSize][1100];

struct list_type
{
    char s[30];
} list[50];

vector <int> g[maxSize];

bool cmp(list_type a, list_type b)
{
    for (int i = 0; i < n; i ++)
        if (a.s[i] < b.s[i])
            return true;
        else if (a.s[i] > b.s[i])
            return false;
    return true;
}

void add_node()
{
    g[total].clear();
    for (int i = 0; i < 26; i ++)
        edge[total][i] = -1;
    total ++;
}

void insert_trie(int now, int k)
{
    if (k == len)
    {
        if (g[now].size() == 0)
        {
            g[now].push_back(num);
            num ++;
        }
        return ;
    }
    if (edge[now][s[k] - 'a'] == -1)
    {
        edge[now][s[k] - 'a'] = total;
        add_node();
    }
    insert_trie(edge[now][s[k] - 'a'], k + 1);
}

void init()
{
    num = total = 0;
    add_node();
    for (int i = 0; i < m; i ++)
    {
        scanf("%s", s);
        len = strlen(s);
        insert_trie(0, 0);
    }
    m = num;
}

void make()
{
    int t = 0;
    for (int i = 0; i < 26; i ++)
        if (edge[0][i] != -1)
        {
            que[t] = edge[0][i];
            fail[que[t]] = 0;
            t ++;
        }
        else
            edge[0][i] = 0;

    for (int h = 0; h < t; h ++)
    {
        int now = que[h];
        for (int i = 0; i < 26; i ++)
            if (edge[now][i] != -1)
            {
                int v = edge[now][i];
                int r = fail[now];
                while (edge[r][i] == -1)
                    r = fail[r];
                fail[v] = edge[r][i];
                for (unsigned int j = 0; j < g[fail[v]].size(); j ++)
                    g[v].push_back(g[fail[v]][j]);
                que[t] = v;
                t ++;
            }
    }
}

void make_print(int now, int v, int p)
{
    if (now == 0)
    {
        for (int i = 0; i <= n; i ++)
            list[num].s[i] = s[i];
        num ++;
        return ;
    }
    for (int i = 0; i < 26; i ++)
        for (int j = 0; j < total; j ++)
        {
            int u = j;
            while (edge[u][i] == -1)
                u = fail[u];
            if (edge[u][i] == v)
            {
                int t = 0;
                for (unsigned int k = 0; k < g[v].size(); k ++)
                    t += (1 << g[v][k]);
                for (int pp = 0; pp <= p; pp ++)
                {
                    if ((pp | t) != p)
                        continue;
                    if (f[now - 1][j][pp] > 0)
                    {
                        s[now - 1] = i + 'a';
                        make_print(now - 1, j, pp);
                    }
                }
            }
        }
}

struct stack_type
{
    int now, v, p;
} stack[maxLen];

void solve()
{
    make();

    memset(f, 0, sizeof(f));
    f[0][0][0] = 1;
    stack[0].now = 0;
    stack[0].v = 0;
    stack[0].p = 0;
    for (int h = 0, t = 1; h != t; h = (h + 1) % maxLen)
    {
        int v = stack[h].v;
        int now = stack[h].now;
        int p = stack[h].p;
        for (int i = 0; i < 26; i ++)
        {
            int u = v;
            while (edge[u][i] == -1)
                u = fail[u];
            u = edge[u][i];
            int pp = p;
            for (unsigned int j = 0; j < g[u].size(); j ++)
                if ((pp & (1 << g[u][j])) == 0)
                    pp += (1 << g[u][j]);
            if (now + 1 < n && f[now + 1][u][pp] == 0)
            {
                stack[t].now = now + 1;
                stack[t].v = u;
                stack[t].p = pp;
                t = (t + 1) % maxLen;
            }
            f[now + 1][u][pp] += f[now][v][p];
        }
    }

    int p = 1 << m;
    long long ans = 0;
    for (int i = 0; i < total; i ++)
        ans += f[n][i][p - 1];
    printf("%lld suspects\n", ans);

    if (ans <= 42)
    {
        num = 0;
        s[n] = '\0';
        for (int i = 0; i < total; i ++)
            if (f[n][i][p - 1] > 0)
                make_print(n, i, p - 1);
        sort(list, list + num, cmp);
        for (int i = 0; i < num; i ++)
            printf("%s\n", list[i].s);
    }
}

int main()
{
    int cnt = 0;
    while (scanf("%d%d", &n, &m) != -1)
    {
        if (n + m == 0)
            break;
        printf("Case %d: ", ++ cnt);
        init();
        solve();
    }
    return 0;
}