• <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 付翔 閱讀(627) 評論(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 算法 是沒有回溯的
              回復  更多評論
              

            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久人爽人人爽人人片AV| 日韩精品久久久久久| 久久SE精品一区二区| 久久久久久久久久久久中文字幕 | 精品久久久久久久久免费影院| 欧美精品九九99久久在观看| 久久99精品久久久久久久久久| 久久www免费人成看国产片| 久久国语露脸国产精品电影| 久久久久久久尹人综合网亚洲| 久久99热这里只有精品66| 狠狠狠色丁香婷婷综合久久俺| 久久夜色精品国产噜噜亚洲a| 国产精品久久久久久久久免费| 97精品伊人久久大香线蕉| 国产午夜电影久久| av无码久久久久不卡免费网站| 国产精品99久久久精品无码| 99久久人人爽亚洲精品美女| 久久精品无码午夜福利理论片| 无码任你躁久久久久久| 久久精品人妻一区二区三区| 狠狠色丁香久久综合婷婷| 久久精品人人槡人妻人人玩AV | 色婷婷噜噜久久国产精品12p| 狠狠色丁香婷综合久久| 久久婷婷五月综合97色| 久久笫一福利免费导航 | 999久久久免费国产精品播放| 色综合久久久久综合体桃花网| 偷偷做久久久久网站| 99久久这里只精品国产免费 | 99久久久国产精品免费无卡顿| 国产成人综合久久精品红| 久久亚洲AV成人无码| 97久久国产综合精品女不卡| 99久久这里只精品国产免费| 亚洲中文字幕无码一久久区| 欧洲精品久久久av无码电影| 国产精品久久久亚洲| 精品国产91久久久久久久|