2つの文字列の最大長の同じサブ文字列を求める

19125 ワード

  1    class Program

  2     {

  3         static void Main(string[] args)

  4         {

  5             string s1 = "abcdefghijklmn";

  6             string s2 = "abc";

  7             string s3 = "bcde";

  8             string s4 = "lmn";

  9             string s5 = "abdef";

 10             string s6 = "bcabcd";

 11             string s7 = "abcdghabcdef";

 12             string s8 = "events/eventinsight/insight";

 13             string s9 = "events";

 14             Console.WriteLine("s1:{0},s1:{1} {2} ", s1, s1, GetMaxSameString(s1, s1));

 15             Console.WriteLine("s1:{0},s2:{1} {2} ", s1, s2, GetMaxSameString(s1, s2));

 16             Console.WriteLine("s2:{0},s3:{1} {2} ", s2, s3, GetMaxSameString(s2, s3));

 17             Console.WriteLine("s3:{0},s4:{1} {2} ", s3, s4, GetMaxSameString(s3, s4));

 18             Console.WriteLine("s4:{0},s5:{1} {2} ", s4, s5, GetMaxSameString(s4, s5));

 19             Console.WriteLine("s1:{0},s6:{1} {2} ", s1, s6, GetMaxSameString(s1, s6));

 20             Console.WriteLine("s1:{0},s7:{1} {2} ", s1, s7, GetMaxSameString(s1, s7));

 21             Console.WriteLine("s8:{0},s9:{1} {2} ", s8, s9, GetMaxSameString(s8, s9));

 22             Console.ReadLine();

 23         }

 24         /// <summary>

 25         ///  index 

 26         /// </summary>

 27         /// <param name="chr"> </param>

 28         /// <param name="str"> </param>

 29         /// <returns>index </returns>

 30         static List<int> GetIndexArr(char chr, string str)

 31         {

 32             List<int> arr = new List<int>();

 33             for (int x = 0, len = str.Length; x < len; x++)

 34             {

 35                 if (chr.Equals(str[x]))

 36                 {

 37                     arr.Add(x);

 38                 }

 39             }

 40             return arr;

 41         }

 42 

 43         /// <summary>

 44         ///  

 45         /// </summary>

 46         /// <param name="list"> </param>

 47         /// <returns> </returns>

 48         static string GetMaxLenString(List<string> list)

 49         {

 50             string str = "";

 51             if (list.Count > 0)

 52             {

 53                 str = list[0];

 54                 for (int k = 0; k < list.Count; k++)

 55                 {

 56                     if (list[k].Length > str.Length)

 57                     {

 58                         str = list[k];

 59                     }

 60                 }

 61             }

 62             return str;

 63         }

 64 

 65         /// <summary>

 66         ///  

 67         /// </summary>

 68         /// <param name="s1"> 1</param>

 69         /// <param name="s2"> 2</param>

 70         /// <returns> </returns>

 71         static string GetMaxSameString(string s1, string s2)

 72         {

 73             List<string> list = new List<string>();

 74             int l1, l2;

 75             string maxStr,minStr;

 76             if (s1.Length > s2.Length)

 77             {

 78                 l1 = s1.Length;

 79                 l2 = s2.Length;

 80                 minStr = s2;

 81                 maxStr = s1;

 82             }

 83             else

 84             {

 85                 l1 = s2.Length;

 86                 l2 = s1.Length;

 87                 minStr = s1;

 88                 maxStr = s2;

 89             }

 90 

 91             for (int i = 0; i < l1; i++)

 92             {

 93                 int j = 0;

 94                 string sb = "";

 95                 char chr = maxStr[i];

 96                 List<int> arr = GetIndexArr(chr, s2);

 97                 for (int y = 0; y < arr.Count; y++)

 98                 {

 99                     j = arr[y];

100                     int k = i;

101                     while (k < l1 && j < l2)

102                     {

103                         if (maxStr[k] == minStr[j])

104                         {

105                             sb += minStr[j];

106                             k++;

107                         }

108                         j++;

109                     }

110                     if (sb.Length > 0)

111                     {

112                         list.Add(sb);

113                         sb = "";

114                     }

115                 }

116             }

117             return GetMaxLenString(list);

118         }

119     }