hdu 1711(kmp算法) - dblank

hdu 1711(kmp算法)

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.
题意:就是在一个串里面找一个子串,并返回下标。
代码:
#include<iostream>
#include<set>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
int numa[1000100], numb[10010], Next[10010], m, n;
void getnext()
{
      Next[0] = -1;
      int  i = 0, j = -1;
      while(i != m - 1)
      {
          if(j == -1 || numb[i] == numb[j])
          {
              ++i;
              ++j;
              Next[i] = j;
          }
          else
          {
              j = Next[j];
          }
      }
}
int kmp()
{
    getnext();
    int i = 0, j = 0;
    while(i != n && j != m)
    {
        if(j == -1 || numa[i] == numb[j])
        {
            i++;
            j++;
        }
        else
        {
            j = Next[j];
        }
    }
    if(j == m)
        return i - j + 1;
    else
        return -1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 0; i<n; i++)
            scanf("%d", &numa[i]);
        for(int i =0; i<m; i++)
            scanf("%d", &numb[i]);
        printf("%d\n", kmp());
    }
    return 0;
}

相关文章

已有 5 条评论
  1. CaseyAdush

    Show more...

    CaseyAdush 回复
  2. Lelandtiz

    301 Moved Permanently
    301 Moved Permanently>>>

    Lelandtiz 回复
  3. Angelosib

    No matter how you do it, losing weight is an individual thing. Friends can help you but they can't lose the weight for you. You've got to take charge of your weight loss from the beginning if you want to get serious about losing weight. The following tips will help.

    Angelosib 回复
  4. CaseyAdush

    Some people, especially those running on busy daily schedules tend to use the pills to help maintain weight since they can not afford to follow all the diet programs. This is not advised. It is recommended that one seek advice from a professional in this field before using the pills. This can save one from many dangers associated with the misuse.

    The diet pills should always be taken whole. Some people tend to divide the pills to serve a longer period of time. This is not advised and can lead to ineffectiveness. If it is required that one takes a complete tablet, it means that a certain amount of the ingredients are required to achieve the desired goal. It is also recommended that one does not crush the pill and dissolve it in beverages. Chemicals found in beverages have the potential of neutralizing the desired nutrients in the pill thereby leading to ineffectiveness. The best way to take the tablets is swallowing them whole with a glass of water.

    The diet pills speed up the metabolic processes. This is the key factor that leads to the burning of all the fats in the body. This means that one passes out lots of urine, which subsequently leads to dehydration. It is imperative that the user take lots of water round the clock. This will help curb dehydration, which can lead to health problems. In addition to that, water offers the required medium for the function of the nutrients and elimination of the fats.

    When buying the review of diet pills, it is imperative that one gets the most recommended dose. People tend to compromise the quality and effectiveness of the tablets due to the variation in cost. The low priced pills depict poor quality, which means their effectiveness is not reliable. Some have also been found to cause health problems. The dose should also be taken as recommended. Over dose will not speed up the process but rather lead to complication. This will increase risk of side effects. If the taking of the pill is forgotten, do not take more to compensate for the lost time.

    The diet plan enclosed with the diet pills has also to be followed. According to the requirements, the termination of the diet must be done even with no results. This means your body is irresponsive.

    CaseyAdush 回复
  5. RobertIdoca

    Doctor Who is now considered a British Institute and has come a long way since it first aired on November 23rd 1963. The very first show saw the Doctor travel 100,00 years into the past to help some dim cavemen discover light. After 26 seasons and seven Doctors later the series came off our screens in 1989 much to the disappointment of the huge devoted fanbase. In 1996 an attempt was made to revive Doctor Who but it wasnt until June 2005 when it came back with a vengeance with Christopher Eccleston as the ninth Doctor that put the series back on the map as it were. It then went on for 5 years with David Tenant portraying the Doctor until 2010 when Matt Smith took over the role. Today it is still a great family show and has attracted many new fans.
    https://www.cialissansordonnancefr24.com/cialis-en-suisse/

    RobertIdoca 回复
发表新评论