字符串算法复习(三)

上一篇: 字符串算法复习(二)
下一篇: 字符串算法复习(四)

BZOJ 4032

题目大意:给两个小写字符串A和B, 问:
A的一个最短的不是B的子串的子串的长度
A的一个最短的不是B的子序列的子串的长度
A的一个最短的不是B的子串的子序列的长度
A的一个最短的不是B的子序列的子序列的长度
len ≤ 2000

解题报告

诡异的题目…但真的很好

T1:

对B串构建后缀自动机, 然后拿A串的每一个后缀去跑即可。

T3:

对B串构建后缀自动机, 然后设状态 dp[i][j] 表示A串处理到位置i, 与之匹配的B的SAM的节点是j, dp即可。

接下来介绍LAM, 子序列自动机。
顾名思义, 每一个子序列在字符串对应的LAM上都不会跑到非法状态。
构造LAM可以倒着贪心地构造, 对于每个字符保存它最后出现的位置即可。

T2:

把A的每一个后缀扔到B上跑即可..

T4:

类似T3, 在LAM上dp。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
using namespace std;
const int MAXL = 4020;
const int INF  = 0x3f3f3f3f;

namespace SAM {
    const int MAXD = MAXL*2;
    struct Node {
        int ch[26];
        int pre, mxd;
    } d[MAXD];
    int dtot = 1, lst = 1;
    void insert (int ch) {
        int u = lst, nu = ++dtot;
        d[nu].mxd = d[u].mxd+1;
        lst = nu;
        while(u && d[u].ch[ch] == 0)
            d[u].ch[ch] = nu, u = d[u].pre;
        if(u == 0) d[nu].pre = 1;
        else {
            int v = d[u].ch[ch];
            if(d[v].mxd == d[u].mxd+1) d[nu].pre = v;
            else {
                int nv = ++dtot;
                d[nv] = d[v]; // clone node
                d[nv].mxd = d[u].mxd+1;
                d[v].pre = d[nu].pre = nv;
                while(u && d[u].ch[ch] == v)
                    d[u].ch[ch] = nv, u = d[u].pre;
            }
        }
    }
    int feed (char * str) {
        int u = 1, cnt = 0;
        while(*str != '\0') {
            cnt ++;
            u = d[u].ch[*str-'a'];
            if(!u) return cnt;
            ++ str;
        }
        return INF;
    }
}
namespace LAM {
    const int MAXD = MAXL*2;
    struct Node {
        int ch[26];
    } d[MAXD];
    int dtot, cur[26];
    void insert (char ch) {
        memcpy(d[++dtot].ch, cur, sizeof cur);
        cur[ch] = dtot;
    }
    int feed (char * str) {
        int u = dtot, cnt = 0;
        while(*str != '\0') {
            ++ cnt;
            u = d[u].ch[*str-'a'];
            if(!u) return cnt;
            ++ str;
        }
        return INF;
    }
}
char A[MAXL], B[MAXL];
int lenA, lenB;
int solve1 () {
    int ans = 0x3f3f3f3f;
    for(int i = 0; i<lenA; i++)
        ans = min(ans, SAM :: feed(A+i));
    if(ans >= INF) ans = -1;
    return ans;
}
int solve2 () {
    int ans = 0x3f3f3f3f;
    for(int i = 0; i<lenA; i++)
        ans = min(ans, LAM :: feed(A+i));
    if(ans >= INF) ans = -1;
    return ans;
}
int dp[2][MAXL*2];
void solve3 () {
    using namespace SAM;
    memset(dp, 0x3f, sizeof dp);
    dp[0][1] = 0;
    for(int i = 0; i<lenA; i++) {
        for(int j = 0; j<=dtot; j++)
            dp[!(i&1)][j] = dp[i&1][j];
        for(int j = 1; j<=dtot; j++)
            dp[!(i&1)][d[j].ch[A[i]-'a']]
            = min(dp[i&1][j]+1, dp[!(i&1)][d[j].ch[A[i]-'a']]);
    }
    if(dp[lenA&1][0] >= INF) dp[lenA&1][0] = -1;
    printf("%d\n", dp[lenA&1][0]);
}
void solve4() {
    using namespace LAM;
    memset(dp, 0x3f, sizeof dp);
    dp[0][dtot] = 0;
    for(int i = 0; i<lenA; i++) {
        for(int j = 0; j<=dtot; j++)
            dp[!(i&1)][j] = dp[i&1][j];
        for(int j = 1; j<=dtot; j++)
            dp[!(i&1)][d[j].ch[A[i]-'a']]
            = min(dp[i&1][j]+1, dp[!(i&1)][d[j].ch[A[i]-'a']]);
    }
    if(dp[lenA&1][0] >= INF) dp[lenA&1][0] = -1;
    printf("%d\n", dp[lenA&1][0]);
}
int main () {
    scanf("%s%s", A, B);
    lenA = strlen(A), lenB = strlen(B);
    for(int i = 0; i<lenB; i++) SAM :: insert(B[i]-'a');
    for(int i = lenB-1; i>=0; i--) LAM :: insert(B[i]-'a');
    LAM :: insert(0);
    printf("%d\n", solve1());
    printf("%d\n", solve2());
    solve3(), solve4();
}

BZOJ 3998

题目大意:给定T和一个长度为N的字符串S，求它的第K小子串是什么。
若T等于0, 那么不同位置的相同子串算1次, 否然算多次。
N ≤ 500000

解题报告

神奇题
首先对S搞出后缀自动机。
当T等于0时, 后缀自动机的每个节点所代表的字符串集合之间都没有交集, 每一条从根节点出发的不同路径都相当于一个本质不同的子串, 所以直接统计即可。
当T等于1时, 一个子串可以出现多次, 那么节点u能走到几个终止节点(一个终止节点是否可以统计多次我还不清楚)就表示u代表的子串是多少个不同后缀的前缀, 就在原串中出现过多少次。
搞。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
using namespace std;
typedef long long LL;
const int MAXL = 500050;
const int INF  = 0x3f3f3f3f;
int T;
namespace SAM {
    const int MAXD = MAXL*2;
    struct Node {
        int ch[26];
        int pre, mxd;
    } d[MAXD];
    int dtot = 1, lst = 1;
    void insert (int ch) {
        int u = lst, nu = ++dtot;
        lst = nu, d[nu].mxd = d[u].mxd+1;
        while(u && !d[u].ch[ch]) d[u].ch[ch] = nu, u = d[u].pre;
        if(u == 0) d[nu].pre = 1;
        else {
            int v = d[u].ch[ch];
            if(d[v].mxd == d[u].mxd+1) d[nu].pre = v;
            else {
                int nv = ++dtot;
                d[nv] = d[v];
                d[nv].mxd = d[u].mxd+1;
                d[v].pre = d[nu].pre = nv;
                while(u && d[u].ch[ch] == v)
                    d[u].ch[ch] = nv, u = d[u].pre;
            }
        }
    }
    bool vis[MAXD];
    LL sum[MAXD], cnt[MAXD];
    void dfs (int u) {
        if(!u || vis[u]) return ;
        for(int ch = 0; ch<26; ch++) {
            dfs(d[u].ch[ch]);
            cnt[u] += cnt[d[u].ch[ch]];
            sum[u] += sum[d[u].ch[ch]];
        }
        if(T == 0) cnt[u] = 1;
        if(u == 1) cnt[u] = 0;
        sum[u] += cnt[u];
        vis[u] = true;
        return ;
    }
    void buildProp () {
        int u = lst;
        while(u != 1) cnt[u] = 1, u = d[u].pre;
        dfs(1);
    }

    void solve (int u, int rest) {
        //printf("at:%d, rest:%d\n", u, rest);
        if(rest <= cnt[u]) return ;
        rest -= cnt[u];
        for(int i = 0; i<26; i++) {
            if(rest > sum[d[u].ch[i]]) rest -= sum[d[u].ch[i]];
            else {putchar(i+'a'); solve(d[u].ch[i], rest); return ;}
        }
    }
}
char str[MAXL];
int main () {
    int K;
    scanf("%s", str);
    scanf("%d%d", &T, &K);
    int len = strlen(str);
    for(int i = 0; i<len; i++) SAM :: insert(str[i]-'a');
    SAM :: buildProp();
    if(SAM :: sum[1] < K) puts("-1");
    else SAM :: solve(1, K);
}
/*
aabbbacbabcbba
1 13
aabbbacba
*/

BZOJ 3926

题目大意:给一棵树, 树上每个节点有一个字符c[i], 问树上所有有向路径组成的字符串中本质不同的字符串数量。
树的叶子节点保证小于等于20。

解题报告

首先对每个叶子节点为根建立Trie树, 然后把所有Trie树合并, 发现原树上每条路径必然是Trie树上某个字符串的后缀。
对Trie树建立广义后缀自动机(就是能够匹配Trie树上所有字符串的子串的后缀自动机), 这个可以利用Trie树上很多字符串拥有同一公共前缀的性质线性建立出来。
然后再后缀自动机上询问不同子串数量即可…

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 100100;
int N, C;
int colr[MAXN];
namespace SAM {
    struct Node {
        int ch[10];
        int pre, mxd, mnd;
    } d[MAXN*20*2];
    int dtot = 1;
    int insert (int ch, int u) {
        int nu = ++dtot;
        d[nu].mxd = d[u].mxd+1;
        while(u && !d[u].ch[ch]) d[u].ch[ch] = nu, u = d[u].pre;
        if(!u) d[nu].pre = 1;
        else {
            int v = d[u].ch[ch];
            if(d[v].mxd == d[u].mxd+1) d[nu].pre = v;
            else {
                int nv = ++dtot;
                d[nv] = d[v];
                d[nv].mxd = d[u].mxd+1;
                d[v].pre = d[nu].pre = nv;
                while(u && d[u].ch[ch] == v) d[u].ch[ch] = nv, u = d[u].pre;
            }
        }
        return nu;
    }
    LL solve () {
        LL ans = 0;
        for(int i = 1; i<=dtot; i++)
            ans += d[i].mxd-d[d[i].pre].mxd;
        return ans;
    }
}
namespace Trie {
    struct Node {
        int ch[10];
    } d[MAXN*20];
    int dtot;
    void build (int u, int p) {
        for(int i = 0; i<C; i++)
            if(d[u].ch[i]) build(d[u].ch[i], SAM :: insert(i, p));
    }
}
namespace Main {
    struct Node {
        int v, nxt;
    } d[MAXN*2];
    int etot, head[MAXN];
    inline void addEdge (int a, int b) {
        etot ++;
        d[etot].v = b;
        d[etot].nxt = head[a];
        head[a] = etot;
    }
    int rad[MAXN];
    void dfs (int u, int f, int t) {
        if(Trie :: d[t].ch[colr[u]] == 0)
            Trie :: d[t].ch[colr[u]] = ++(Trie :: dtot);
        int nt = Trie :: d[t].ch[colr[u]];
        for(int e = head[u]; e; e = d[e].nxt)
            if(d[e].v != f) dfs(d[e].v, u, nt);
    }
    void solve() {
        scanf("%d%d", &N, &C);
        for(int i = 1; i<=N; i++) scanf("%d", &colr[i]);
        for(int i = 1; i<N; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            addEdge(a, b), addEdge(b, a);
            rad[a]++, rad[b]++;
        }
        for(int i = 1; i<=N; i++)
            if(rad[i] == 1) dfs(i, 0, 0);
        Trie :: build(0, 1);
        cout << SAM :: solve();
    }
}

int main () {Main :: solve();}

BZOJ 2946

题目大意:给你N个长度不超过2000的字符串, 问它们的最长公共子串。
N≤5

解题报告

N×2000^2哈希貌似也可以做…还是继续练习SAM。
直接对除了第一个串以外的每个串建立后缀自动机然后枚举第一个串的后缀喂给后缀自动机吃即可。

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 2020;
const int MAXD = MAXN*2;
struct SAM {
    struct Node {
        int ch[26];
        int pre, mxd;
    } d[MAXD];
    int dtot, lst;
    SAM () {dtot = lst = 1;}
    void insert (int ch) {
        int nu = ++dtot, u = lst;
        lst = nu;
        d[nu].mxd = d[u].mxd+1;
        while(u && !d[u].ch[ch]) d[u].ch[ch] = nu, u = d[u].pre;
        if(!u) d[nu].pre = 1;
        else {
            int v = d[u].ch[ch];
            if(d[v].mxd == d[u].mxd+1) d[nu].pre = v;
            else {
                int nv = ++dtot;
                d[nv] = d[v];
                d[v].pre = d[nu].pre = nv;
                d[nv].mxd = d[u].mxd+1;
                while(u && d[u].ch[ch] == v) d[u].ch[ch] = nv, u = d[u].pre;
            }
        }
    }
    int feed (char * str) {
        int u = 1, cnt = 0;
        while(*str != '\0') {
            u = d[u].ch[*str-'a'];
            if(!u) return cnt;
            ++ cnt;
            ++ str;
        }
        return cnt;
    }
} sam[4];
int N;
char strs[5][2020];
int main () {
    scanf("%d", &N);
    for(int i = 1; i<=N; i++)
        scanf("%s", strs[i-1]);
    for(int i = 2; i<=N; i++) {
        int len = strlen(strs[i-1]);
        for(int j = 0; j<len; j++)
            sam[i-2].insert(strs[i-1][j]-'a');
    }
    int len = strlen(strs[1]);
    int ans = 0;
    for(int i = 0; i<len; i++) {
        int mx = 0x3f3f3f3f;
        for(int j = 0; j<N-1; j++)
            mx = min(mx, sam[j].feed(strs[0]+i));
        ans = max(ans, mx);
    }
    printf("%d\n", ans);
}
//2

BZOJ 3238

题目大意:
盗图!

解题报告

sa+单调栈维护面积乱搞。
貌似可以在后缀自动机的fail树上进行Dp, lca就是prefix, 但是我懒就不写另一种方法了…

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXL = 500050;

int buk[MAXL], mem[2][MAXL];
void suffixArray (char * str, int len, int chr, int * sa) {
    int * x = mem[0], * y = mem[1];
    memset(buk, 0, sizeof buk);
    for(int i = 0; i<len; i++) ++ buk[x[i] = str[i]];
    for(int i = 1; i<chr; i++) buk[i] += buk[i-1];
    for(int i = len-1; i>=0; i--) sa[--buk[x[i]]] = i;
    for(int cur = 1, p = 0; p+1<len; chr = p+1, cur<<=1) {
        p = 0;
        for(int i = len-cur; i<len; i++) y[p++] = i;
        for(int i = 0; i<len; i++) if(sa[i] >= cur) y[p++] = sa[i]-cur;
        memset(buk, 0, sizeof buk);
        for(int i = 0; i<len; i++) ++ buk[x[y[i]]];
        for(int i = 1; i<chr; i++) buk[i] += buk[i-1];
        for(int i = len-1; i>=0; i--) sa[--buk[x[y[i]]]] = y[i];
        swap(x, y); x[sa[0]] = 0; p = 0;
        for(int i = 1; i<len; i++)
            x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+cur] == y[sa[i-1]+cur]) ? p : ++p;
    }
}

void suffixHeight (char * str, int len, int chr, int * sa, int * he, int * rk) {
    str[len] = '\0';
    suffixArray(str, len+1, chr, sa);
    for(int i = 0; i<=len; i++)
        rk[sa[i]] = i;
    int k = 0;
    for(int i = 0; i<len; i++) {
        for(k?k--:k; str[i+k] == str[sa[rk[i]-1]+k]; ++k) ;
        he[rk[i]] = k;
    }
}

char str[MAXL];
int stk[MAXL], val[MAXL], stktop;
int sa[MAXL], he[MAXL], rk[MAXL];
int main () {
    scanf("%s", str);
    int len = strlen(str);
    suffixHeight(str, len, 'z'+1, sa, he, rk);
    LL S = 0, ans = 0;
    for(int i = 1; i<=len; i++) {
        while(stktop && val[stktop] >= he[i]) {
            S -= (LL)(stk[stktop]-stk[stktop-1])*val[stktop];
            stktop --;
        }
        stk[++ stktop] = i, val[stktop] = he[i];
        if(stktop != 1) S += (LL)(stk[stktop]-stk[stktop-1])*he[i];
        ans -= S*2;
        ans += (LL)i*(i-1)+(LL)i*(i-1)/2;
    }
    printf("%I64d\n", ans);
}

BZOJ 2882

题目大意:给字符串, 求最小表示。

解题报告

模板, PE了不想管了。
我真是越来越懒了…题解都懒得写了…

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 600060;
int N;
int arr[MAXN];
int main () {
    scanf("%d", &N);
    for(int i = 1; i<=N; i++)
        scanf("%d", &arr[i]);
    for(int i = N+1; i<=(N<<1); i++)
        arr[i] = arr[i-N];
    int i = 1, j = 2, k = 0;
    while(i+k <= N && j+k <= N) {
        if(arr[i+k] == arr[j+k]) k++;
        else {
            if(arr[i+k] < arr[j+k]) j += k+1;
            else i = j, j = j+1;
            k = 0;
        }
    }
    for(int x = i; x<i+N; x++)
        printf("%d ", arr[x]);
}

BZOJ 2555

题目大意:
一开始有一个串T, 进行两种操作:
1.给定串S, 查询它在T中出现了多少次。
2.给定串S, 把S插入到T的末尾。
强制在线。

解题报告

建立后缀自动机。
如果主链上节点u(就是每次扩展自动机时插入的节点)的fail边指向v, 那么意味着所有substrings(v)都是longest(u)(原串前缀)的后缀, 就代表它们在不同位置出现了一次。
那么在后缀自动机上统计单个节点在fail树上子树内主链节点个数就可以了。
理解起来好困难…
强制在线, 用lct维护这个值。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXL = 600060;
const int MAXQL = 3000030;
namespace LCT {
    struct Node {
        int ch[2], fa;
        int lz, cnt;
        bool tfa;
    } d[MAXL*2];
    int dtot;
    void add (int u, int v) {d[u].lz += v, d[u].cnt += v;}
    void pushdown (int u) {
        if(d[u].lz) {
            if(d[u].ch[0]) add(d[u].ch[0], d[u].lz);
            if(d[u].ch[1]) add(d[u].ch[1], d[u].lz);
            d[u].lz = 0;
        }
    }
    void downlazy (int u) {
        if(d[u].tfa) downlazy(d[u].fa);
        pushdown(u);
    }
    void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        swap(d[y].tfa, d[x].tfa);
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        if(d[x].tfa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
    }
    void splay (int x) {
        downlazy(x);
        while(d[x].tfa) {
            int y = d[x].fa;
            int z = d[y].fa;
            if(d[y].tfa) {
                if((d[z].ch[0] == y) == (d[y].ch[0] == x))
                    rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
    void access (int u) {
        int t = u, r = 0;
        while(u) {
            splay(u);
            d[d[u].ch[1]].tfa = false;
            d[d[u].ch[1] = r].tfa = true;
            r = u, u = d[u].fa;
        }
        splay(t);
    }
    void cut (int u) {
        access(u);
        d[d[u].ch[0]].tfa = false;
        d[d[u].ch[0]].fa = 0;
        add(d[u].ch[0], -d[u].cnt);
        d[u].ch[0] = 0;
    }
    void link (int u, int v) {
        if(!u) return ;
        access(u);
        access(v);
        d[v].fa = u;
        add(u, d[v].cnt);
    }
    int qSize (int u) {
        access(u);
        return d[u].cnt;
    }
}
namespace SAM {
    const int MAXD = MAXL*2;
    struct Node {
        int ch[26];
        int pre, mxd;
    } d[MAXD];
    int dtot = 1, lst = 1;
    inline void insert (int ch) {
        int u = lst, nu = ++dtot;
        LCT :: d[nu].cnt = 1;
        lst = nu;
        d[nu].mxd = d[u].mxd+1;
        while(u && !d[u].ch[ch]) d[u].ch[ch] = nu, u = d[u].pre;
        if(!u) d[nu].pre = 1, LCT :: link(1, nu);
        else {
            int v = d[u].ch[ch];
            if(d[v].mxd == d[u].mxd+1) d[nu].pre = v, LCT :: link(v, nu);
            else {
                int nv = ++dtot;
                d[nv] = d[v];
                d[nv].mxd = d[u].mxd+1;
                d[nu].pre = d[v].pre = nv;
                LCT :: cut(v);
                LCT :: link(nv, nu), LCT :: link(nv, v), LCT :: link(d[nv].pre, nv);
                while(u && d[u].ch[ch] == v) d[u].ch[ch] = nv, u = d[u].pre;
            }
        }
        //LCT :: access(nu);
        //LCT :: add(nu, 1);
    }
    inline void hinsert (char * str) {
        while(*str != '\0') insert(*str-'A'), ++str;
    }
    inline int feed (char * str) {
        int u = 1;
        while(*str != '\0') {
            u = d[u].ch[*str-'A'];
            if(!u) return 0;
            ++ str;
        }
        return u;
    }
}
void decode (char * s, int mask) {
    int len = strlen(s);
    for(int j = 0; j<len; j++) {
        mask = (mask*131+j)%len;
        char t = s[j];
        s[j] = s[mask];
        s[mask] = t;
    }
}
char bufs[20], bufl[MAXQL];
int main () {
    int Q, mask = 0;
    scanf("%d", &Q);
    scanf("%s", bufl);
    SAM :: hinsert(bufl);
    while(Q --) {
        scanf("%s%s", bufs, bufl);
        decode(bufl, mask);
        //printf("trueStr:%s\n", bufl);
        if(bufs[0] == 'A')
            SAM :: hinsert(bufl);
        else {
            int u = SAM :: feed(bufl);
            if(u == 0) {puts("0"); continue ;}
            int ans = LCT :: qSize(u);
            printf("%d\n", ans);
            mask ^= ans;
        }
    }
    int dbg;
    dbg = 0;
}
/*
10
A
QUERY A
ADD BBABAA
QUERY AAB
ADD ABBBABBBBBBABABBABBBA
QUERY ABA
*/

BZOJ 2553

题目大意: 自己看…

解题报告

一开始觉得就是AC自动机+矩阵快速幂算期望傻逼题…
但是想了一会发现自己居然不会构建这个矩阵!
看完题解才发现自己犯傻了, 单独开出一个节点X保留答案, 每次匹配上之后贪心地选择断开(必然最优), 然后把期望累加到X上去, 跳回根节点即可。
记得下传匹配的mark。
据说卡double? 开long double。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXL = 100;
int dicsz;
namespace Trie {
    const int MAXD = MAXL;
    struct Node {
        int ch[26], pre;
        bool mark;
    } d[MAXD];
    int dtot;
    void insert (char * str) {
        int u = 0;
        while(*str != '\0') {
            if(!d[u].ch[*str-'a'])
                d[u].ch[*str-'a'] = ++dtot;
            u = d[u].ch[*str-'a'];
            ++ str;
        }
        d[u].mark = true;
    }
    long double mat[MAXD][MAXD];
    queue<int> que;
    void setup () {
        que.push(0);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(int ch = 0; ch<dicsz; ch++) {
                if(d[u].ch[ch]) {
                    int v = d[u].ch[ch];
                    if(d[u].pre != u)
                        d[v].pre = d[d[u].pre].ch[ch];
                    d[v].mark |= d[d[v].pre].mark;
                    que.push(v);
                } else d[u].ch[ch] = d[d[u].pre].ch[ch];
            }
        }
        long double posb = (long double)1.0/dicsz;
        for(int u = 0; u<=dtot; u++)
            for(int ch = 0; ch<dicsz; ch++)
                if(d[d[u].ch[ch]].mark) mat[u][0] += posb, mat[u][dtot+1] += posb;
                else mat[u][d[u].ch[ch]] += posb;
        mat[dtot+1][dtot+1] = 1.0;
    }
    void mul (long double (*A)[MAXD], long double (*B)[MAXD], long double (*C)[MAXD], int N) {
        for(int i = 0; i<N; i++)
            for(int j = 0; j<N; j++)
                for(int k = 0; k<N; k++)
                    C[i][j] += A[i][k]*B[k][j];
    }
    long double tmp1[MAXD][MAXD], tmp2[MAXD][MAXD];
    double solve (int len) {
        memcpy(tmp2, mat, sizeof mat);
        memset(mat, 0, sizeof mat);
        for(int i = 0; i<=dtot+1; i++)
            mat[i][i] = 1;
        while(len) {
            if(len&1) {
                memcpy(tmp1, mat, sizeof mat);
                memset(mat, 0, sizeof mat);
                mul(tmp1, tmp2, mat, dtot+2);
            }
            memcpy(tmp1, tmp2, sizeof tmp2);
            memset(tmp2, 0, sizeof tmp2);
            mul(tmp1, tmp1, tmp2, dtot+2);
            len >>= 1;
        }
        return mat[0][dtot+1];
    }
}
char buf[100];
int main () {
    int N, len;
    scanf("%d%d%d", &N, &len, &dicsz);
    for(int i = 1; i<=N; i++) {
        scanf("%s", buf);
        Trie :: insert(buf);
    }
    Trie :: setup();
    printf("%.8lf\n", Trie :: solve(len));
}