一、内容
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
Input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
Sample Output
2
2
二、思路
– 暴力枚举子串即可。 注意子串还需要左右颠倒比较一次。
三、代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
char s[N][N], p[N];
int t, n, m, k, mx, ne[N];
void getNext() {ne[1] = 0;for (int i = 2, j = 0; i <= m; i++) {while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] != p[j + 1]) j++;ne[i]= j;}
}
bool kmp(int k) {n = strlen(s[k] + 1);getNext();for (int i = 1, j = 0; i <= n; i++) {while (j && s[k][i] != p[j + 1]) j = ne[j];if (s[k][i] == p[j + 1]) j++;if (j == m) return true; } //左右颠倒 reverse(p + 1, p + 1 + m);getNext();for (int i = 1, j = 0; i <= n; i++) {while (j && s[k][i] != p[j + 1]) j = ne[j];if (s[k][i] == p[j + 1]) j++;if (j == m) return true; } return false;
}
bool ok() {for (int i = 1; i <= k; i++) {if (!kmp(i)) return false;}return true;
}
int main() {scanf("%d", &t);while (t--) {scanf("%d", &k);for (int i = 1; i <= k; i++) scanf("%s", s[i] + 1);n = strlen(s[1] + 1); mx = 0;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {m = j - i + 1;for (int h = i; h <= j; h++) p[h - i + 1] = s[1][h];p[m + 1] = '\0';if (ok() && m > mx) mx = m;} }printf("%d\n", mx);} return 0;
}