• <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>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            posts - 106,  comments - 32,  trackbacks - 0
            今天碰見一個赤裸裸的 kmp 算法的題 直接找了個模板 但是卻一直WA
            后來 查自己的數據結構的書 改動一下
                //if( pat[j] > 0) return -2;
                
            //else return i-j;
                return ((j==b)?(i-b) :-2);
            后來就過了 郁悶 確實對于kmp 算法不是很熟啊
            很是杯具

            # include<stdio.h>
            # include
            <string.h>
            int fail[10000+1];
            long a,b;
            int kmp(int* str, int* pat){
                
            int i, j, k;
                memset(fail, 
            -1sizeof(fail));
                
            //fail[0] = 0;
                for (i = 1; i<b; ++i) {
                    
            for (k=fail[i-1]; k>=0 && pat[i]!=pat[k+1];k=fail[k]);
                    
            if (pat[k + 1== pat[i]) fail[i] = k + 1;
                    
            //if(k == 0)  fail[i] = k + 1;
                }
                i 
            = j = 0;
                
            while( i< a && j < b ){ // By Fandywang
                    if( pat[j] == str[i] ) ++i, ++j;
                    
            else if(j == 0)++i;//第一個字符匹配失敗,從str下個字符開始
                    else j = fail[j-1]+1; }
                
            //if( pat[j] > 0) return -2;
                
            //else return i-j;
                return ((j==b)?(i-b) :-2);
            }
            int src[1000000+1];
            int dest[10000+1];
            int main()
            {
                
            int T,i;
                
                freopen(
            "1284.txt","r",stdin);
                scanf(
            "%d",&T);
                
            while(T--)
                {
                    scanf(
            "%ld%ld\n",&a,&b);
                    
            for(i = 0; i < a; i ++)
                        scanf(
            "%d",&src[i]);
                   
            // src[i] = '\0';
                    for(i = 0; i < b; i ++)
                        scanf(
            "%d",&dest[i]);
                   
            // dest[i] = '\0';
                    printf("%d\n",kmp(src,dest)+1);
                    
                    
                }
                
            return 0;
            }


            posted on 2010-07-26 19:42 付翔 閱讀(634) 評論(2)  編輯 收藏 引用 所屬分類: ACM 數據結構

            FeedBack:
            # re: hdu 1711 kmp 算法
            2010-07-30 18:34 | smztsmzt
            請教一下 關于串匹配的KMP算法問題

            KMP中的主串指針不用回溯,下面的串匹配怎么進行:請教一下
            位數: 1 2 3 4 5
            主串: a a a a b
            模式串: a a a b

            如果主串指針不用回溯,可以發現主串包含模式串么?想不明白。
              回復  更多評論
              
            # re: hdu 1711 kmp 算法
            2010-08-02 13:21 | 付翔
            @smztsmzt
            KMP 算法 是沒有回溯的
              回復  更多評論
              

            <2011年5月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久青草国产手机看片福利盒子| 少妇精品久久久一区二区三区| 欧美一区二区精品久久| 色综合合久久天天给综看| 亚洲av伊人久久综合密臀性色| Xx性欧美肥妇精品久久久久久| 久久久久亚洲AV无码专区首JN| 精品国产VA久久久久久久冰| 精品久久久无码中文字幕天天| 久久精品国产亚洲AV无码麻豆 | 蜜臀av性久久久久蜜臀aⅴ| 天天久久狠狠色综合| 久久精品国产亚洲av麻豆蜜芽| 91精品国产综合久久香蕉| 久久亚洲日韩精品一区二区三区| 色婷婷狠狠久久综合五月| www.久久热| 91精品国产色综合久久| 亚洲精品高清国产一线久久| 亚洲国产精品无码久久青草| 久久99精品国产麻豆蜜芽| 国产一区二区三区久久精品| 久久99精品久久久大学生| 尹人香蕉久久99天天拍| 国产精品内射久久久久欢欢| 丁香狠狠色婷婷久久综合| 无码国内精品久久人妻| 久久丫忘忧草产品| 久久笫一福利免费导航| 欧美性大战久久久久久| 久久亚洲中文字幕精品一区四 | 人妻精品久久无码区| 亚洲精品乱码久久久久久| 亚洲国产精品无码久久98| 欧美激情一区二区久久久| 久久久噜噜噜久久中文字幕色伊伊 | 久久亚洲国产成人精品性色| 性欧美丰满熟妇XXXX性久久久 | 欧美黑人激情性久久| 日韩精品国产自在久久现线拍 | 久久久久精品国产亚洲AV无码|