• <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>

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            HDU 1711 HDOJ 1711 Number Sequence ACM 1711 IN HDU

            Posted on 2010-10-05 14:17 MiYu 閱讀(776) 評論(0)  編輯 收藏 引用 所屬分類: ACM ( 串 )
            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

             

             

            題目地址 :

                 http://acm.hdu.edu.cn/showproblem.php?pid=1711

            題目描述:

            代碼
            Number Sequence

            Time Limit: 
            10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 
            1926    Accepted Submission(s): 819


            Problem Description
            Given two sequences of numbers : a[
            1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 100001 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1= b[2], ...... , a[K + M - 1= b[M]. If there are more than one K exist, output the smallest one.
             

            Input
            The first line of input 
            is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 100001 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-10000001000000].
             

            Output
            For each test 
            case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
             

            Sample Input
            2
            13 5
            1 2 1 2 3 1 2 3 1 3 2 1 2
            1 2 3 1 3
            13 5
            1 2 1 2 3 1 2 3 1 3 2 1 2
            1 2 3 2 1
             

            Sample Output
            6
            -1
             

             

             代碼

            題目分析 :
               很久以前做的一個題目,  純粹的套模板了..... 到現在還是沒明白 KMP 到底怎么回事, 也可能是我沒花時間去仔細的看的原因.

            今天上郵箱發現一個星期前一位網友問我的1711代碼速度為什么那么快, 著到代碼一看, 原來是個 簡單的KMP 裸題, 直接模板就行了,

            速度的話這里有個小技巧, 知道的人就不要笑話我了.  

            其實關鍵就是 對輸入數據的 加速
            !!!!
            一般對數據的輸入都是 
            %d 或 %%lf 對吧?  其實計算機讀取的數據是字符形的, 它也需要調用其他的函數將這個串轉換成
            數字,  所以你只要 用字符串讀入 數據,  然后自己寫個函數 把 這個字符串轉換成 數字久行了.

            其實呢, 很多題目都可以只要來加速的, 除非它的數據量不大.


            下面是我的代碼 : 


            #include 
            <iostream>
            using namespace std;
            const int MAXN=1000000;
            const int MAXM=10000;

            int nn[MAXN+1],mm[MAXM+1];
            int Fail[MAXM+1];

            void GetFail(int num[],int m){
                    Fail[
            0]=-1;
                    
            for(int i=1,j=-1;i<m;i++){
                            
            while(j>=0&&num[j+1]!=num[i]){
                                    j
            =Fail[j];
                            }
                            
            if(num[j+1]==num[i])j ++;
                            Fail[i]
            =j;
                    }
            }
            int KMP(int numA[],int numB[],int n,int m){
                    GetFail ( numB,m );    
                    
            for (int i=0,j=0;i<n;i++){
                            
            while(j&&numB[j]!=numA[i]){
                                    j
            =Fail[j-1]+1;
                            }
                            
            if(numB[j]==numA[i]) j++;
                            
            if(j == m) return i-m+2;
                    }
                    
            return -1;
            }
            inline 
            bool scan_d(int &num)  //  這個就是 加速的 關鍵了 
            {
                    
            char in;bool IsN=false;
                    
            in=getchar();
                    
            if(in==EOF) return false;
                    
            while(in!='-'&&(in<'0'||in>'9')) in=getchar();
                    
            if(in=='-'){ IsN=true;num=0;}
                    
            else num=in-'0';
                    
            while(in=getchar(),in>='0'&&in<='9'){
                            num
            *=10,num+=in-'0';
                    }
                    
            if(IsN) num=-num;
                    
            return true;
            }
            int main ()
            {
                
            int N,M,T;
                
            while ( scan_d(T) )
                {
                       
            while ( T -- )
                       {
                              scan_d(N),scan_d(M);
                              
            for ( int i = 0; i != N; ++ i )
                                  scan_d ( nn[i] );
                              
            for ( int j = 0; j != M; ++ j )
                                  scan_d ( mm[j] );    
                              printf ( 
            "%d\n",KMP ( nn,mm,N,M ) );  
                       }
                }
                
            return 0;
            }
            久久久久99这里有精品10| 88久久精品无码一区二区毛片 | 久久这里有精品视频| 亚洲精品国产字幕久久不卡| 99久久99久久精品免费看蜜桃| 久久99毛片免费观看不卡 | 国产 亚洲 欧美 另类 久久| 久久人人爽人人爽人人片AV不 | 国产精品久久国产精麻豆99网站| 久久国产精品-国产精品| 久久精品三级视频| 日本久久久久久中文字幕| 久久亚洲精品无码aⅴ大香| 国产精品免费久久久久影院| 日日狠狠久久偷偷色综合96蜜桃| 久久亚洲AV成人无码电影| 色欲综合久久躁天天躁| 久久天天躁狠狠躁夜夜96流白浆| 99精品久久久久久久婷婷| 18岁日韩内射颜射午夜久久成人| 久久天天躁狠狠躁夜夜2020老熟妇 | 久久久久亚洲av无码专区导航| 亚洲国产成人精品久久久国产成人一区二区三区综| 人人狠狠综合久久亚洲| 国内精品久久久久影院优| 97精品久久天干天天天按摩 | 亚洲精品高清国产一线久久| 日韩欧美亚洲综合久久影院d3| 国产69精品久久久久9999APGF| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 久久无码专区国产精品发布| 国产精品欧美亚洲韩国日本久久| 性欧美丰满熟妇XXXX性久久久| 久久无码AV中文出轨人妻| 久久亚洲国产中v天仙www| 久久综合88熟人妻| 亚洲va久久久噜噜噜久久狠狠| 中文字幕精品久久久久人妻| 久久人妻无码中文字幕| 天天影视色香欲综合久久| 欧美久久一级内射wwwwww.|