2744: 子串
总时间限制: 1000ms 内存限制: 65536kB
描述
现在有一些由英文字符组成的大小写敏感的字符串, 你的任务是找到一个最长的字符串 x, 使得对于已经给出的字符串中的任意一个 y,x 或者是 y 的子串, 或者 x 中的字符反序之后得到的新字符串是 y 的子串.
输入
输入的第一行是一个整数 t (1 <= t <= 10),t 表示测试数据的数目. 对于每一组测试数据, 第一行是一个整数 n (1 <= n <= 100), 表示已经给出 n 个字符串. 接下来 n 行, 每行给出一个长度在 1 和 100 之间的字符串.
输出
对于每一组测试数据, 输出一行, 给出题目中要求的字符串 x 的长度.
样例输入
- 2
- 3
- ABCD
- BCDFF
- BRCD
- 2
- rose
- orchid
样例输出
2
2
问题链接: Bailian2744 子串 https://cn.vjudge.net/problem/OpenJ_Bailian-2744
问题描述:(略)
问题分析:
???? 这是一个字符串处理问题, 需要熟悉字符串处理函数的使用. 用枚举法进行处理计算.
程序说明:(略)
参考链接:(略)
题记:(略).
AC 的 C 语言程序如下:
- /* Bailian2744 子串 */
- #include <stdio.h>
- #include <string.h>
- #define MIN(a, b) (((a) <(b)) ? (a) : (b))
- #define N 100
- char s[N][N + 1], sub[N + 1], rev[N + 1];
- void strrev(char s[])
- {
- int i = 0, j = strlen(s) - 1;
- char c;
- while(i < j) {
- c = s[i];
- s[i] = s[j];
- s[j] = c;
- i++;
- j--;
- }
- }
- int maxSubString(char t[], int n)
- {
- int sublen, srclen, flag, i, j;
- sublen = srclen = strlen(t);
- while(sublen> 0) {
- for(i = 0; i <= srclen - sublen; i++) {
- strncpy(sub, t + i, sublen);
- strncpy(rev, t + i, sublen);
- sub[sublen] = rev[sublen] = '\0';
- strrev(rev);
- flag = 1;
- for(j = 0; j < n; j++) {
- if(strstr(s[j], sub) == NULL && strstr(s[j], rev) == NULL) {
- flag = 0;
- break;
- }
- }
- if(flag)
- return sublen;
- }
- sublen--;
- }
- return 0;
- }
- int main(void)
- {
- int t, n, minlen, pos, i;
- scanf("%d", &t);
- while(t--) {
- scanf("%d", &n);
- minlen = N;
- for(i = 0; i < n; i++) {
- scanf("%s", s[i]);
- minlen = MIN(minlen, (int)strlen(s[i]));
- }
- /* 找出最短串位置 */
- for(i = 0; i < n; i++)
- if((int)strlen(s[i]) == minlen) {
- pos = i;
- break;
- }
- /* 输出结果 */
- printf("%d\n", maxSubString(s[pos], n));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2900994.html