1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 111; 9 int dp[maxn][maxn], parent[maxn], len[maxn];10 char DNA[maxn][maxn];11 12 int LCS(int a, int b)13 {14     int ans = 0;15     memset(dp,0,sizeof(dp));16     for(int i = 1; i <= len[a]; ++i)17         for(int j = 1; j <= len[b]; ++j)18         {19             if(DNA[a][i-1] == DNA[b][j-1])20                 dp[i][j] = dp[i-1][j-1] + 1;21             if(dp[i][j] > ans)22                 ans = dp[i][j];23         }24     return ans;25 }26 27 int GetParent(int a) 28 {29     return parent[a] == a ? a : parent[a] = GetParent(parent[a]);30 }31 32 int main(void)33 {34     #ifdef LOCAL35         freopen("2144in.txt", "r", stdin);36     #endif37 38     int n, kase = 0;39     double p;40     while(scanf("%d %lf", &n, &p) == 2)41     {42         for(int i = 0; i < n; ++i)43         {44             scanf("%s", DNA[i]);45             parent[i] = i;46             len[i] = strlen(DNA[i]);47         }48         for(int i = 0; i < n; ++i)49             for(int j = 0; j < i; ++j)50             {51                 int pi = GetParent(i);52                 int pj = GetParent(j);53                 if(pi == pj)    continue;54                 double x = LCS(i, j) * 100.0;55                 if(x/len[i]>p && x/len[j]>p)56                     parent[pi] = pj;57             }58         int ans = 0;59         for(int i = 0; i < n; ++i)60             if(parent[i] == i)61                 ++ans;62         printf("Case %d:\n%d\n", ++kase, ans);63     }64     return 0;65 }