题目大意：给你m串字符串，要你找最长的相同的连续字串
这题暴力kmp即可，注意要按字典序排序，同时，是len<3才输出no significant commonalities
1 #include2 #include 3 #include 4 #include 5 #define MAX 60 6 7 using namespace std; 8 9 typedef char* _String; 10 typedef int Position; 11 static char str[11][61],ans[62]; 12 static int _next[62]; 13 14 bool KmpSearch(_String, _String, const int); 15 void Get_Next(_String, const int); 16 void Search(const int); 17 18 int main(void)//暴力枚举第一行 19 { 20 int case_sum, m; 21 //freopen("in.txt", "r", stdin); 22 scanf("%d", &case_sum); 23 24 while (case_sum--) 25 { 26 scanf("%d", &m); 27 getchar(); 28 29 for (int i = 0; i < m; i++) 30 scanf("%s", str[i]); 31 Search(m); 32 } 33 return EXIT_SUCCESS; 34 } 35 36 void Search(const int m) 37 { 38 int len, ans_len = -1, pos, if_match; 39 char tmp; 40 41 for (len = 1; len <= MAX; len++) 42 { 43 for (pos = 0; pos + len <= MAX; pos++) 44 { 45 if_match = 0; 46 Get_Next(&str[0][pos], len); 47 for (int i = 1; i < m; i++) 48 if_match += KmpSearch(str[i], &str[0][pos], len); 49 if (if_match == m - 1 && len >= ans_len) 50 { 51 if (len == ans_len) 52 { 53 tmp = str[0][pos + len]; 54 str[0][pos + len] = '\0'; 55 if (strcmp(&str[0][pos], ans) < 0) 56 strcpy(ans, &str[0][pos]); 57 str[0][pos + len] = tmp; 58 } 59 else if (len > ans_len) 60 { 61 ans_len = len; 62 tmp = str[0][pos + len]; 63 str[0][pos + len] = '\0'; 64 strcpy(ans, &str[0][pos]); 65 str[0][pos + len] = tmp; 66 } 67 } 68 } 69 } 70 if (ans_len < 3) 71 printf("no significant commonalities\n"); 72 else 73 printf("%s\n", ans); 74 } 75 76 bool KmpSearch(_String str_m, _String text, const int t_len) 77 { 78 Position i = 0, j = 0; 79 80 while (i < MAX && j < t_len) 81 { 82 if (j == -1 || str_m[i] == text[j]) 83 { 84 i++; 85 j++; 86 } 87 else j = _next[j]; 88 } 89 if (j == t_len) 90 return true; 91 else 92 return false; 93 } 94 95 void Get_Next(_String text, const int t_len) 96 { 97 Position i = 0, k = -1; 98 _next[0] = -1; 99 100 while (i < t_len)101 {102 if (k == -1 || text[i] == text[k])103 {104 i++;105 k++;106 _next[i] = text[i] != text[k] ? k : _next[k];107 }108 else k = _next[k];109 }110 }
