0012-子串

问题描述

一些由英文字符组成的大小写敏感的字符串。请写一个程序,找到一个最长的字符串 x,使得:对于已经给出的字符串中的任意一个 y,x 或者是 y 的子串、或者 x 中的字符反序之后得到的新字符串是 y 的子串。

输入

输入的第一行是一个整数 t (1 <= t <= 10),t 表示测试数据的数目。对于每一组测试数据,第一行是一个整数 n (1 <= n <= 100),表示已经给出 n 个字符串。接下来 n 行,每行给出一个长度在 1 和 100 之间的字符串。

输出

对于每一组测试数据,输出一行,给出题目中要求的字符串 x 的长度;如果找不到符合要求的字符串,则输出 0。

输入样列

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

输出样例

2
2

算法实现

using System;

namespace Questions{
    class Program{
        public static void Main(string[] args)
        {
            string input = Console.ReadLine();
            int t = int.Parse(input);
            string minStr = "";
            while (t!=0) {
                t--;
                input = Console.ReadLine();
                int n = int.Parse(input);
                string[] str = new string[n];
                int minStrLen = 101;
                for (int i = 0; i < n; i++) {
                    input = Console.ReadLine();
                    str[i] = input;
                    if (str[i].Length < minStrLen) {
                        minStr = str[i];
                        minStrLen = str[i].Length;
                    }
                }
                //查找最大子串
                int len = SearchMaxSubString(str,minStr);
                Console.WriteLine(len);
            }
            Console.ReadKey();
        }
        /// <summary>
        /// 查找最大子串
        /// </summary>
        /// <param name="str">字符串数组</param>
        /// <param name="minStr">字符串数组中长度最短的字符串</param>
        /// <returns></returns>
        public static int SearchMaxSubString(string[] str, string minStr) {
            int minStrlen = minStr.Length;
            int subStrlen = minStr.Length;
            bool isFound = true;
            string revSubStr = "", subStr = "";
            while (subStrlen > 0) {
                for (int i = 0; i <=minStrlen - subStrlen; i++) {
                    //获取minStr中从下标i开始长度为subStrlen的子串
                    subStr = minStr.Substring(i,subStrlen);
                    revSubStr = StrRev(subStr);
                    isFound = true;
                    for (int j = 0; j < str.Length; j++) {
                        //IndexOf在字符串str[j]中寻找参数字符串subStr第一次出现的位置并返回该位置，未查找到返回-1
                        if (str[j].IndexOf(subStr) == -1 && str[j].IndexOf(revSubStr) == -1) {
                            isFound = false;
                            break;
                        }
                    }
                    if (isFound)
                        return subStrlen;
                }
                subStrlen--;
            }
            return 0;
        }
        /// <summary>
        /// 字符串逆序
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        public static string StrRev(string str) {
            string revStr = "";
            for (int i = str.Length - 1; i >= 0; i--) {
                revStr += str[i];
            }
            return revStr;
        }
    }
}