KMP模板題|hdu 1711

數(shù)據(jù)大

#include<iostream>
#include<string.h>
#define maxn 1000000+5
#define maxn2 10000+5
using namespace std;

int s[maxn];
int p[maxn2];
int Next[maxn2];
void getNext(const int p[],int Next[],int plen) {
    Next[0]=-1;
    int k=-1;
    int j=0;
    while(j<plen-1) {
        if(k==-1||p[k]==p[j]) {
            ++k;
            ++j;
            if(p[k]!=p[j])
                Next[j] = k;
            else
                Next[j] = Next[k];//修正nNext數(shù)組

        }

        else {
            k = Next[k];
        }
    }
}

int KMP(const int s[],const int p[],int slen,int plen) {

    int i=0;
    int j=0;
    while(i<slen&&j<plen) {
        if(j==-1||s[i]==p[j]) {
            i++;
            j++;
        } else {
            j = Next[j];
        }
    }

    if(j>=plen) {
        return i-j+1;
    } else {
        return -1;
    }

}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int num1,num2;
        cin>>num1;
        cin>>num2;
        for(int i=0; i<num1; i++)
            scanf("%d",&s[i]);
        for(int i=0; i<num2; i++)
            scanf("%d",&p[i]);
        memset(Next,-1,sizeof(Next));
        getNext(p,Next,num2);
        //cout<<*Next<<endl;
        cout<<KMP(s,p,num1,num2)<<endl;
    }

    return 0;
}

http://acm.split.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): 30758 Accepted Submission(s): 12930

Problem Description

Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= 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 <= 10000, 1 <= 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 [-1000000, 1000000].

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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子府树,更是在濱河造成了極大的恐慌拓巧,老刑警劉巖笤昨,帶你破解...
    沈念sama閱讀 216,470評論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異儿礼,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)宫静,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,393評論 3 392
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來券时,“玉大人孤里,你說我怎么就攤上這事「镂” “怎么了扭粱?”我有些...
    開封第一講書人閱讀 162,577評論 0 353
  • 文/不壞的土叔 我叫張陵舵鳞,是天一觀的道長震檩。 經(jīng)常有香客問我,道長蜓堕,這世上最難降的妖魔是什么抛虏? 我笑而不...
    開封第一講書人閱讀 58,176評論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮套才,結(jié)果婚禮上迂猴,老公的妹妹穿的比我還像新娘。我一直安慰自己背伴,他們只是感情好沸毁,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,189評論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著傻寂,像睡著了一般息尺。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上疾掰,一...
    開封第一講書人閱讀 51,155評論 1 299
  • 那天搂誉,我揣著相機(jī)與錄音,去河邊找鬼静檬。 笑死炭懊,一個(gè)胖子當(dāng)著我的面吹牛并级,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播侮腹,決...
    沈念sama閱讀 40,041評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼嘲碧,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了父阻?” 一聲冷哼從身側(cè)響起呀潭,我...
    開封第一講書人閱讀 38,903評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎至非,沒想到半個(gè)月后钠署,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,319評論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡荒椭,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,539評論 2 332
  • 正文 我和宋清朗相戀三年谐鼎,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片趣惠。...
    茶點(diǎn)故事閱讀 39,703評論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡狸棍,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出味悄,到底是詐尸還是另有隱情草戈,我是刑警寧澤,帶...
    沈念sama閱讀 35,417評論 5 343
  • 正文 年R本政府宣布侍瑟,位于F島的核電站唐片,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏涨颜。R本人自食惡果不足惜费韭,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,013評論 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望庭瑰。 院中可真熱鬧星持,春花似錦、人聲如沸弹灭。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,664評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽穷吮。三九已至逻翁,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間酒来,已是汗流浹背卢未。 一陣腳步聲響...
    開封第一講書人閱讀 32,818評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人辽社。 一個(gè)月前我還...
    沈念sama閱讀 47,711評論 2 368
  • 正文 我出身青樓伟墙,卻偏偏與公主長得像,于是被迫代替她去往敵國和親滴铅。 傳聞我的和親對象是個(gè)殘疾皇子戳葵,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,601評論 2 353

推薦閱讀更多精彩內(nèi)容