查找两个字符串的最长公共子串(附源码)_AX

查找两个字符串a,b中的最长公共子串
【思路】遍历a的字符,每次取出一个字符与b进行匹配(遍历b),如匹配上,a,b同时后移一个字符,再循环遍历b进行匹配,直到匹配不上,把刚才匹配的公共字串与已知最长子串进行比较,如果它比最长子串还长,替换最长子串,如相等,也保存.

【缺陷】本来优化了一下,减少了些不必要的循环次数,结果发现如果没有公共子串就会出现数组越界问题,可以改一下判断条件,但整个结构就会感觉很乱就删除了,只剩了一句做为注释掉,大家可以自己优化一下.

【总结】本来思路很简单,但调试起来还是用了很多时间,主要是因为变量初始化放的位置不对.相对菜鸟而言,思路跟代码实现还是有段距离的.
【源码】

 1using System;
 2using System.Collections;
 3namespace CompareString_AX
 4{
 5    /**//// <summary>
 6    /// Class1 的摘要说明。
 7    /// </summary>
 8    class Class1
 9    {
10        /**//// <summary>
11        /// 应用程序的主入口点。
12        /// </summary>
13        [STAThread]
14        static void Main(string[] args)
15        {
16            string a="AX_skljfgfdeerterter";//12315aaa1aaaa1211213412222";
17            string b="AX_weesdfsdee1";//31222aaaa1aaa1113412222";
18            ArrayList AX=Compare(a,b);
19            foreach(string i in AX)
20            {
21                Console.WriteLine("最长的子串为："+i);
22            }
23            Console.ReadLine();
24        }
25        public static ArrayList Compare(string a,string b)
26        {                        
27            ArrayList arr=new ArrayList();
28            arr.Add("");
29            //循环遍历字符串a
30            for(int i=0;i<a.Length;i++)
31            {                                
32                //在字符串b中查找从匹配上a[i]开始的子串
33                //优化循环次数(有点问题)for(int j=0;j<b.Length-arr[0].ToString().Length+1;j++)
34                for(int j=0;j<b.Length;j++)
35                {
36                    int n=1;//计数器
37                    string subTemp="";//保存匹配上的临时子串
38                    char tempa=a[i];
39                    char tempb=b[j];
40                    //匹配上后，两字符串的字符同时后移一位，再进行匹配，直到匹配不上
41                    while(tempa==tempb)
42                    {
43                        subTemp+=tempa;
44                        if((i+n)<a.Length&&(j+n)<b.Length)
45                        {
46                            tempa=a[i+n];
47                            tempb=b[j+n];
48                            n++;
49                        }
50                        else
51                        {
52                            break;
53                        }
54                    }
55                    //比较子串与临时子串的长度
56                    if(subTemp.Length>arr[0].ToString().Length&&subTemp.Length!=0)
57                    {
58                        arr.Clear();
59                        arr.Add(subTemp);
60                    }
61                    else if(subTemp.Length==arr[0].ToString().Length&&subTemp.Length!=0)
62                    {
63                        arr.Add(subTemp);
64                    }
65                }
66            }
67            //设置返回值            
68            if(arr[0].ToString().Length!=0)
69            {
70                return arr;
71            }
72            else
73            {
74                arr.Clear();
75                arr.Add("没有共同的子串！");
76                return arr;
77            }
78        }
79    }
80}
81