蛙蛙 上午發的一片 蛙蛙推薦：[算法練習]最長不完全匹配子串頻率計算 ， eaglet 看了以後，也寫了一個算法，用蛙蛙給的兩個參數測試，速度大概比蛙蛙的快800倍左右。如果字符串更長，速度差異會更明顯。

算法描述：找出一個長字符串裏的某個特定的子串出現的頻率，匹配的子串的上一個字符和下一個字符不需要緊緊相鄰，只要滿足下一個字符在當前字符的後面就行。
算法要求：長字符串的寬度最長是500個字符。
輸入：一個長字符串，寬度不能超過500個字符，一個短字符串
輸出：短字符串在長字符串中出現的次數的後四位，不足四位左邊填充零。
舉例來説：在“wweell”字符串中找“wel”出現的次數，可以匹配到8次，應輸出0008，每個匹配子串的索引序列分別如下 

0,2,4
0,2,5
0,3,4
0,3,5
1,2,4
1,2,5
1,3,4
1,3,5

算法分析

這個題目要求輸出匹配次數，如果用蛙蛙的方法，反覆遞歸查找，算法複雜度很高，有沒有辦法把算法複雜度降低到 O(n) 呢，答案是有的。首先我們分析這個題目，不難看出，這個出現次數等於每個被匹配分量上出現次數的乘積。

拿上面的參數為例，被匹配字符串為 wel , 劃分為 w e l 三個分量，這三個分量在原字符串中出現次數分別是 2 2 2 則其出現次數為 2*2*2 = 8

當然程序設計是還要考慮順序的問題，不過這就是小問題了，這裏就不討論的。有了這個大思路，eaglet 編寫了如下代碼


presto 匹配 子串_presto 匹配 子串

      

public static void Eaglet(string source, string sub)
        
{
            Console.WriteLine(string.Format("{0:0000}", EagletMatch(source, sub)));
        }

        private static int EagletMatch(string source, string sub)
        
{
            int[] hitCountArrary = new int[sub.Length]; //sub 字串每個分類在source 中的命中次數

            int i = 0;
            bool lastMatched = false;

            //順序掃描source字符串
            foreach (char c in source)
            
{
                if (c == sub[i])
                
{
                    //如果當前值和當前分量匹配，相應分量統計加一
                    hitCountArrary[i]++;
                    lastMatched = true;
                }
                else
                
{
                    if (lastMatched)
                    
{
                        i++;
                        if (i >= sub.Length)
                        
{
                            //重頭繼續查找
                            i = 0;
                        }
                        else
                        
{
                            if (c == sub[i])
                            
{
                                //如果當前值和當前分量匹配，相應分量統計加一
                                hitCountArrary[i]++;
                            }
                            else
                            
{
                                //如不匹配，往下匹配
                                lastMatched = false;

                                if (i >= sub.Length)
                                
{
                                    //重頭繼續查找
                                    i = 0;
                                }
                            }
                        }
                    }
                }
            }

            int result = 1;

            //計算乘積
            foreach (int count in hitCountArrary)
            
{
                result *= count;
            }

            //輸出匹配的次數
            return result;
        }

presto 匹配 子串_presto 匹配 子串

 

這個代碼算法複雜度為 O(n) ，計算蛙蛙給的兩個參數

private static string math = "welcome to cnblogs";
private static string test_input = "wweellccoommee to cnblogs";

結果為0128 和蛙蛙的結果一致，執行時間只有蛙蛙的 1/800.