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 }