find common substrings in 2 string in c#

Question

I have strings like:

1) Cookie:ystat_tw_ss376223=9_16940400_234398;
2) Cookie:zynga_toolbar_fb_uid=1018132522

3) GET /2009/visuels/Metaboli_120x600_UK.gif HTTP/1.1
4) GET /2010/07/15/ipad-3hk-smv-price-hk/ HTTP/1.1

1 ad 2 have common substtring{cookie:} 3 and 4 have common substtring{GET /20, HTTP/1.1}

I want to find all common substrings that have the length more than three characters(contain space character) between 2 strings.(like 1 and 2) i want to code in c#. i have a program but it has some problems.

Could anyone help me?

    public static string[] MyMCS2(string a, string b)
    {          
        string[] st = new string[100];
       // List<string> st = new List<string>();
        List<char> f = new List<char>();
        int ctr = 0;                     
        char[] str1 = a.ToCharArray();
        char[] str2 = b.ToCharArray();
        int m = 0;
        int n = 0;
        while (m < str1.Length)
        {
            for (n = 0; n < str2.Length; n++)
            {
                if (m < str1.Length)
                {
                    if (str1[m] == str2[n])
                    {
                        if ((m > 1) && (n > 1) &&(str1[m - 1] == str2[n - 1]) && (str1[m - 2] == str2[n - 2]))
                        {
                            //f[m]= str1[m];
                            f.Add(str1[m]);

                            char[] ff = f.ToArray();
                            string aaa = new string(ff);

                            if (aaa.Length >= 3)
                            {
                                st[ctr] = aaa + "()";
                                //st.Add(aaa);

                                ctr++;                               
                            }


                            kk = m;
                            m++;
                        }                         

                        else if ((n == 0) ||(n == 1))
                        {
                            f.Add(str1[m]);
                            kk = m;
                            m++;
                        }

                        else
                            f.Clear();
                    }
                    //else  if ((str1[m] == str2[n]) && (m == str1.Length - 1) && (n == str2.Length - 1))
                    //{
                    //    f.Add(str1[m]);
                    //    char[] ff = f.ToArray();
                    //    string aaa = new string(ff);

                    //    if (aaa.Length >= 3)
                    //    {
                    //        st[ctr] = aaa;
                    //        ctr++;
                    //    }
                    //   // m++;
                    //}

                    else if ((str1[m] != str2[n]) && (n == (str2.Length - 1)))
                    {
                        m++;
                    }

                    else if ((m > 1) && (n > 1) && (str1[m] != str2[n]) && (str1[m - 1] == str2[n - 1]) && (str1[m - 2] == str2[n - 2]) && (str1[m - 3] == str2[n - 3]))
                    {
                        //
                        char[] ff = f.ToArray();
                        string aaa = new string(ff);

                        if (aaa.Length >= 3)
                        {
                            st[ctr] = aaa + "()" ;
                            //st.Add(aaa);

                            ctr++;
                            f.Clear();
                        }
                        //f.Clear();

                        //for (int h = 0; h < ff.Length; h++)
                        //{
                        //    f[h] = '\0';
                        //}
                    }
                    else if (str1[m] != str2[n])
                        continue;
                }
            }               
        }
        //int gb = st.Length;
        return st;
    }

Answer 1

This is an exact matching problem not a substring. You can solve it with aho-corasick algorithm. Use the first string and compute a finite state machine. Then process the search string. You can extend the aho-corasick algorithm to use a wildcard and search also for substrings. You can try this animated example: http://blog.ivank.net/aho-corasick-algorithm-in-as3.html