• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Problem Solving using C++

            Algorithm Study using C++

            字符串匹配算法(3)---String Matching Algorithm

            由于有限自動機方法與KMP算法類似,并且有限自動機方法在預處理上的時間復雜度比KMP方法高,所以在本文的討論中,暫時不討論有限自動機方法,主要是考慮KMP算法。
            KMP算法是一個非常有名的字符串匹配算法,其由Knuth,Morris和Pratt一起提出來的,預處理時間為O(m),其中m為匹配字符串的長度,匹配時間為O(n),其中n為需要匹配的字符串的長度。
            核心算法如下:
            //預處理部分
            int pi[m];
            pi[0]=0;
            int k = 0;

            for(int i=1;i<m;i++)
            {
               while((k>0)&&(p[i]!=p[k])
                   k=pi[k];

               if(p[i]==p[k])
                   k++;

               pi[i]=k;
            }

            //匹配部分
            int k=0;
            for(int i=0;i<n;i++)
            {
                while((k>0)&&(p[k]!=t[i]))
                       k=pi[k];
             
                 if(p[k]==t[i])
                      k++;

                  if(k==m)
                   {
                        //輸出結果,從(i+1-m)開始已經匹配
                        k=pi[m-1];//開始下一個匹配
                   }
            }

            具體的可運行的實現代碼為:
             1 #include <iostream>
             2 #include <string>
             3 
             4 using namespace std;
             5 
             6 int main(int argc,char* argv[])
             7 {
             8     char *t=NULL,*p=NULL;
             9     int *pi=NULL;
            10     string text,pattern;
            11 
            12     while(1)
            13     {
            14         cin>>text>>pattern;
            15         int n = text.length();        
            16         int m = pattern.length();
            17 
            18         //t= new char[n+1];
            19         //p= new char[m+1];
            20         t= new char[n];
            21         p= new char[m];
            22         pi = new int[m];
            23 
            24         //strcpy(t,text.c_str());
            25         //strcpy(p,pattern.c_str());
            26         memcpy(t,text.data(),n);
            27         memcpy(p,pattern.data(),m);
            28 
            29         //calculate the PI array
            30         int q = 0;
            31         pi[0]=0;
            32 
            33         for(int i=1;i<m;i++)
            34         {
            35             while((q>0)&&(p[q]!=p[i]))
            36             {
            37                 q=pi[q];
            38             }
            39 
            40             if(p[q]==p[i])
            41                 q++;
            42 
            43             pi[i]=q;
            44         }
            45 
            46         //use the KMP matching algorithm
            47         q = 0;
            48         for(int i=0;i<n;i++)
            49         {
            50             while((q>0)&&(p[q]!=t[i]))
            51             {
            52                 q = pi[q];
            53             }
            54 
            55             if(p[q]==t[i])
            56                 q++;
            57 
            58             if(q==m)
            59             {
            60                 cout<<((i+1)-m)<<endl;
            61                 q = pi[m-1];
            62             }
            63         }
            64 
            65         delete[] t;
            66         delete[] p;
            67         delete[] pi;
            68     }
            69 
            70     system("pause");
            71     return 0;
            72 }
            73 


            posted on 2007-08-21 14:37 Kingoal Lee's Alogrithm Study using cplusplus 閱讀(1874) 評論(2)  編輯 收藏 引用

            Feedback

            # re: 字符串匹配算法(3)---String Matching Algorithm 2007-08-23 11:07 金慶

            有錯誤!測試如下,竟輸出2!

            abbbababbbbb
            ababab
            2
              回復  更多評論   

            # re: 字符串匹配算法(3)---String Matching Algorithm 2007-08-23 12:42 Kingoal Lee's Alogrithm Study using cplusplus

            @金慶
            嗯,我剛剛測試了一下,發現上面的出錯。
            非常感謝你給我指出來!

            需要修改的是第52行,將其改為:
            q = pi[q-1];
            抱歉!  回復  更多評論   


            My Links

            Blog Stats

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            欧洲人妻丰满av无码久久不卡| 色综合久久天天综合| 久久久精品国产| 亚洲国产精品无码久久一线| 久久精品国产亚洲精品2020| 国产午夜福利精品久久| 久久一区二区三区99| 天天躁日日躁狠狠久久| 91久久精品视频| 99久久国产综合精品女同图片| 丁香狠狠色婷婷久久综合| 久久精品国产只有精品66| 人妻无码久久一区二区三区免费| 伊人久久大香线焦综合四虎| yy6080久久| 久久精品一区二区三区中文字幕| 亚洲AV无码久久精品成人| 久久99久久无码毛片一区二区| 久久免费的精品国产V∧| 久久久久国产亚洲AV麻豆| 97久久香蕉国产线看观看| 久久久国产打桩机| 久久久亚洲精品蜜桃臀| 国产精品国色综合久久| 无码人妻少妇久久中文字幕| 久久精品国产一区| 国产综合久久久久| 久久精品人人做人人爽电影蜜月| 伊人久久大香线蕉综合5g| 久久久久国产| 久久99国产精品成人欧美| 蜜桃麻豆www久久| 精品久久香蕉国产线看观看亚洲| 久久久无码精品亚洲日韩蜜臀浪潮 | 99久久国产综合精品女同图片| 久久久亚洲精品蜜桃臀 | 品成人欧美大片久久国产欧美| av无码久久久久不卡免费网站| 亚洲av伊人久久综合密臀性色| 久久夜色精品国产噜噜麻豆 | 亚洲AV伊人久久青青草原|