Number Sequence HDU-1711(KMPアルゴリズム理解+テンプレート)
2490 ワード
まず大物のリンクを置いて、ke'yはとても詳しく話しています.https://blog.csdn.net/v_july_v/article/details/7041827、ありがとうございます
この記事では、マッチング値の一部について詳しく説明します.http://www.doc88.com/p-2929643037053.html
kmpに対する私の理解を話しましょう(必ずしも正しいとは限らない、先輩の多zhi'が教えてくれた):
kmpアルゴリズムの優位性は,p上の文字をs上の各文字と比較する必要がなく,時間を節約することである.
例を挙げると、「acbacd」という文字列が最後の文字に一致していないので、前のいくつかの文字の特徴は明らかに私たちが最初から比べる必要はありません.文字「b」から比べることができます.「acbac」の接頭辞「ac」==接尾辞「ac」に相当し、間接的な比に相当します.
nexts[]配列は,部分整合値を1に後退させ,最初の補完−1である.
例題:
Number Sequence
HDU - 1711
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
Sample Output
題意:Tグループデータ、sはn個の数があって、pはm個の数があって、sの中のあの位置からpをマッチングすることができることを聞きます
構想:kmpアルゴリズムテンプレート問題
ACコード:
この記事では、マッチング値の一部について詳しく説明します.http://www.doc88.com/p-2929643037053.html
kmpに対する私の理解を話しましょう(必ずしも正しいとは限らない、先輩の多zhi'が教えてくれた):
kmpアルゴリズムの優位性は,p上の文字をs上の各文字と比較する必要がなく,時間を節約することである.
例を挙げると、「acbacd」という文字列が最後の文字に一致していないので、前のいくつかの文字の特徴は明らかに私たちが最初から比べる必要はありません.文字「b」から比べることができます.「acbac」の接頭辞「ac」==接尾辞「ac」に相当し、間接的な比に相当します.
nexts[]配列は,部分整合値を1に後退させ,最初の補完−1である.
例題:
Number Sequence
HDU - 1711
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 1Sample Output
6
-1題意:Tグループデータ、sはn個の数があって、pはm個の数があって、sの中のあの位置からpをマッチングすることができることを聞きます
構想:kmpアルゴリズムテンプレート問題
ACコード:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include