[字符串操作]1082 子串

1082 子串

题目描述

现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串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

解题分析

这个程序的主要思想是找到给定字符串中最长的子串，这个子串或者是给定字符串的子串，或者这个子串反向后是给定字符串的子串。

首先，程序读取测试数据的数目t，然后对每一组测试数据进行处理。

对于每一组测试数据，程序首先读取字符串的数目n，然后读取每个字符串。在读取字符串的过程中，程序会记录下最短的字符串和它的长度。

然后，程序开始从最短字符串的长度开始，逐一减小，对每一种长度，程序会尝试所有可能的子串（包括正向和反向），并检查这个子串是否存在于所有给定的字符串中。

具体实现是这样的：首先，对于从长度等于最短字符串长度到长度等于1的每一个长度，程序会尝试从最短字符串的开头开始，取长度为当前长度的所有可能的子串，然后对每一个子串，程序会生成它的反向字符串，然后对于给定的所有字符串，检查子串或者反向字符串是否是它的子串。

如果找到了一个子串，它自己或者它的反向字符串是所有给定字符串的子串，那么程序就找到了一个满足要求的最长子串，然后输出这个子串的长度并结束当前测试数据的处理。

如果对于一个长度，程序没有找到满足要求的子串，那么程序就会继续尝试长度减1的子串。

如果对于所有的长度，程序都没有找到满足要求的子串，那么程序就会输出0，并结束当前测试数据的处理。

代码实现

#include <stdio.h>
#include <string.h>

int main(void) { 
	int t; scanf("%d",&t);
	while(t--){
		int n; scanf("%d",&n);
		char words[105][105];
		int minlen; char minstr[105];
		for(int i=0;i<n;i++){
			scanf("%s",words[i]);
			if(i==0){
				minlen=strlen(words[i]);
				strcpy(minstr,words[i]);
			}
			else{
				int len=strlen(words[i]);
				if(len<minlen){
					minlen=len;
					strcpy(minstr,words[i]);
				}
			}
		}
		char reverseStr[105],subStr[105];
		int foundMax=1;
		for(int i=minlen;i>0;i--){
			for(int j=0;j+i<=minlen;j++){
				strncpy(subStr,minstr+j,i);
				strncpy(reverseStr,minstr+j,i);
				subStr[i]=reverseStr[i]='\0';
				for(int k=0,m=i-1;k<=m;k++,m--){
					char temp=reverseStr[k];
					reverseStr[k]=reverseStr[m];
					reverseStr[m]=temp;
				}
				for(int k=0;k<n;k++){
					if(strstr(words[k],subStr)==NULL && strstr(words[k],reverseStr)==NULL){
						foundMax=0;
						break;
					}
					if(k==n-1){
						foundMax=1;
					}
				}
				if(foundMax){
					printf("%d\n",i);
					break;
				}
			}
			if(foundMax) break;
		}
		if(foundMax==0) printf("0\n");
	}
	return 0;
}