Alice and Bob both have lots of candies but want more. They decide to play the following turn-based game.
First they write some words on a few pieces of paper and put them into a bag so they cannot see the words. Next they decide whose turn is first. The first turn begins with the first player drawing and keeping a piece of paper with the word A from the bag and copying A onto a blackboard evenly spaced.
Then the second player draws and keeps a piece of paper with the word B on it. The current player is to write B on the blackboard underneath A evenly spaced. The second player receives one candy from the first for each character that matches vertically between A and B.
Now it is the first player’s turn who similarly draws and places word C underneath B and gains a candy for each of the characters vertically matched between B and C. The game continues until there are no more words in the bag.
What is the maximum number of candies that one of Alice and Bob can possibly get in a turn?
The game on the second blackboard awards the second player one candy.
The game on the third blackboard awards the second player two candies.
Input
The first line of the input contains an integer t (1 ≤ t ≤ 70), the number of test cases. Each test case
starts with an integer n (2 ≤ n ≤ 70), the number of words in the bag. Then follow n lines containing
one word each (in no particular order). Each word will contain between 1 and 70 characters, all of
them uppercase letters of English alphabet.
Output
For each test case, print a line containing the maximum number of candies either Alice or Bob can get
in a single turn.
Sample Input
2
2
ALICE
BOB
2
ABCB
BCAB
Sample Output
0
2
问题链接：UVA11548 Blackboard Bonanza
问题简述：（略）
问题分析：文本处理问题，不解释。
程序说明：（略）
参考链接：（略）
题记：（略）
AC的C语言程序如下：
/* UVA11548 Blackboard Bonanza */
#include <stdio.h>
#include <string.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define N 70
char s[N + 1][N + 1];
int judge(char a[], char b[])
{
int lena = strlen(a), ret = 0;
for (int i = 0; a[i]; i++) {
int cnt = 0;
for (int j = 0; b[j]; j++) {
if (i + j == lena) break;
if (a[i + j] == b[j]) cnt++;
}
ret = MAX(ret, cnt);
}
return ret;
}
int main()
{
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s", s[i]);
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j)
ans = MAX(ans, judge(s[i], s[j]));
printf("%d\n", ans);
}
return 0;
}
