先预处理一下数据。。类似求LCS
然后并查集
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip> 10 #include<climits> 11 #include<string.h> 12 #include<cmath> 13 #include<stdlib.h> 14 #include<vector> 15 #include<stack> 16 #include<string.h> 17 #include<set> 18 #define INF 1e7 19 #define MAXN 10010 20 #define maxn 1000010 21 #define Mod 1000007 22 #define N 110 23 using namespace std; 24 typedef long long LL; 25 26 int n; 27 double m; 28 char str[N][N]; 29 int fa[N], len[N], dp[N][N]; 30 31 int findset(int x) 32 { 33 return fa[x] = fa[x] == x ? x : findset(fa[x]); 34 } 35 36 int getlen(int a, int b) 37 { 38 int re = 0; 39 memset(dp[0], 0, sizeof(dp[0])); 40 for (int i = 1; i <= len[a]; i++) 41 { 42 dp[i][0] = 0; 43 for (int j = 1; j <= len[b]; j++) 44 { 45 if (str[a][i] == str[b][j]) dp[i][j] = dp[i - 1][j - 1] + 1; 46 else dp[i][j] = 0; 47 if (re < dp[i][j]) re = dp[i][j]; 48 } 49 } 50 return re; 51 } 52 int main() 53 { 54 int T = 1; 55 int x, y, l; 56 while (cin >> n >> m) 57 { 58 for (int i = 0; i < n; i++) 59 fa[i] = i; 60 for (int i = 0; i < n; i++) 61 { 62 scanf("%s", str[i] + 1); 63 str[i][0] = ' '; 64 len[i] = strlen(str[i]) - 1; 65 for (int j = 0; j < i; j++) 66 { 67 int x = findset(i); 68 int y = findset(j); 69 if (x == y) continue; 70 l = getlen(i, j); 71 if (l*100.0 / len[i] > m && l*100.0 / len[j] > m) 72 fa[x] = y; 73 } 74 } 75 int ans = 0; 76 for (int i = 0; i < n; i++) if (fa[i] == i) ans++; 77 printf("Case %d: %d ", T++, ans); 78 } 79 return 0; 80 }