• <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>
            隨筆 - 7  文章 - 15  trackbacks - 0
            <2006年7月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            常用鏈接

            留言簿(2)

            隨筆檔案(7)

            相冊

            搜索

            •  

            積分與排名

            • 積分 - 15785
            • 排名 - 953

            最新評論

            閱讀排行榜

            評論排行榜

            #i nclude <stdio.h>
            #i nclude <stdlib.h>
            #i nclude <string.h>
            #i nclude <time.h>

            //獲得prefix數組
            int* GetPrefixValue(char* strPattern, int iPatternLen)
            {
            ??? int i, j; /* i runs through the string, j counts the hits*/
            ??? int* prefix = (int*)malloc(iPatternLen*sizeof(int));
            ???
            ??? i = 1; j = 0;
            ??? prefix[0] = 0;
            ???
            ??? while(i<iPatternLen)
            ??? {
            ??????? if(strPattern[i] == strPattern[j])
            ??????? {
            ??????????? prefix[i] = ++j;
            ??????? }
            ??????? else
            ??????? {
            ??????????? j = 0;
            ??????????? prefix[i] = j;
            ??????? }
            ???????
            ??????? i++;
            ??? }
            ???
            ??? return prefix;??????????
            }???

            //返回target串在pattern串中第一次匹配的index
            int KMPStringMatch(char* strPattern, int iPatternLen, char* strTarget, int iTargetLen, int* prefix)
            {
            ??? int i = 0;
            ??? int j = 0;
            ???
            ??? while(i<iPatternLen && j<iTargetLen)
            ??? {
            ??????? if(j==0 || strPattern[i]==strTarget[j])
            ??????? {
            ??????????? i++;? j++;
            ??????? }
            ??????? else
            ??????? {
            ??????????? j = prefix[j];
            ??????? }
            ??? }????????????
            ???
            ??? free(prefix);
            ????
            ??? if(j==iTargetLen)
            ??? {
            ??????? return i-j;
            ??? }
            ??? else
            ??? {
            ??????? return -1;
            ??? }????????
            }????????

            int KMP(char* strPattern, char* strTarget)
            {
            ??? int* prefix = GetPrefixValue(strPattern, strlen(strPattern));
            ??? int index = KMPStringMatch(strPattern, strlen(strPattern), strTarget, strlen(strTarget), prefix);
            ??? return index;
            }

            //在文本文件中查找target串出現的行數
            int SearchInTxtFile(char* fileName, char* strTarget)
            {
            ??? FILE* hFile = fopen(fileName, "r");
            ???
            ??? char str[1024];
            ??? int count = 0;
            ???
            ???
            ??? while(fgets(str, 1024, hFile))?
            ??? {
            ??????? if(KMP(str, strTarget)!=-1)
            ??????? {
            ??????????? count++;
            ??????? }???
            ??? }?????
            ???
            ??? fclose(hFile);
            ??? hFile=NULL;
            ???
            ??? return count;
            }????
            ????????????
            int main()
            {
            ??? char ch;
            ??? char str1[] = "abcabcabctasksb,abTo";
            ??? char str2[] = "abc";
            ???
            ??? double t=clock();
            ??? printf("%d\n", KMP(str1,str2));
            ??? printf("耗時:%f毫秒!\n", (clock()-t));
            ???
            ??? t=clock();
            ??? printf("find %d \n", SearchInTxtFile("c:\\txt.txt", "NULL"));
            ??? printf("耗時:%f毫秒!\n", (clock()-t));
            ??? scanf("%c", &ch);

            ??? return 0;
            }?

            posted on 2006-07-05 23:48 Bourne 閱讀(4782) 評論(4)  編輯 收藏 引用

            FeedBack:
            # re: KMP字符串匹配算法C語言實現 2009-02-18 13:24 楊如清
            錯誤的算法
            char str1[] = "abcabcabctasksb,abTo";
            char str2[] = "sb";
            KMP(str1,str2)返回0  回復  更多評論
              
            # re: KMP字符串匹配算法C語言實現 2009-02-27 19:46 gaewah
            的確好像錯了厄。。
            abaababaab
            的prefix算錯了。。  回復  更多評論
              
            # re: KMP字符串匹配算法C語言實現 2009-08-17 14:45 test
            簡直就一垃圾 這樣的代碼也貼出來!  回復  更多評論
              
            # re: KMP字符串匹配算法C語言實現 2011-06-17 10:04 學校
            樓上有點偏激了。。。  回復  更多評論
              
            久久91精品国产91久| 久久久久亚洲AV成人网人人网站 | 亚洲AV无码1区2区久久| 7777精品久久久大香线蕉| 精品久久久久久无码专区| 国产精品久久影院| 欧美亚洲另类久久综合婷婷| 亚洲AV无码久久精品蜜桃| 日本精品久久久久中文字幕| 女同久久| 国产91久久精品一区二区| 婷婷久久综合| 国产激情久久久久影院| 伊人久久大香线蕉AV色婷婷色| 7国产欧美日韩综合天堂中文久久久久 | 久久www免费人成看国产片| 97视频久久久| 九九热久久免费视频| 久久精品国产亚洲av麻豆色欲| 2021国产成人精品久久| 狠狠综合久久AV一区二区三区| 久久婷婷综合中文字幕| 久久天天躁狠狠躁夜夜avapp | 久久婷婷五月综合97色| 亚洲国产成人久久精品99| 久久国产精品国产自线拍免费| 久久久这里只有精品加勒比| 18岁日韩内射颜射午夜久久成人| 无码AV中文字幕久久专区| 欧美久久一级内射wwwwww.| 伊人久久精品线影院| 国产91久久精品一区二区| 久久人人爽人人爽人人AV东京热| 精品国产乱码久久久久久人妻| 久久久精品人妻无码专区不卡| 7国产欧美日韩综合天堂中文久久久久 | 色婷婷噜噜久久国产精品12p | 久久久久久一区国产精品| 伊人久久大香线蕉精品| 91久久婷婷国产综合精品青草| 亚洲精品高清国产一线久久|