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;
}

### 相关文章

2. 301 Moved Permanently
301 Moved Permanently>>>

Lelandtiz 回复
3. 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. 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.