首页 > 代码库 > hdu 1711 Number Sequence 解题报告

hdu 1711 Number Sequence 解题报告

2024-07-03 17:08:26   236人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1711

题目意思：给出一条有n个数的序列a[1]，a[2]，......，a[n]，和一条有m 个数的序列b[1]，b[2]，......，b[m]，求出b[1]，b[2]，...，b[m]在序列a中完全匹配时，在序列a中的位置，如果找不到输出-1.

        这几天一直在学kmp，该题算是kmp的入门题吧。有个地方要稍稍注意，代码中，主串和模式串的比较初始值为-1，-1，否则如果从0开始，会默认第一个字符是相等的！！！

      

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 1e6 + 5;
 7 const int M = 1e4 + 5;
 8 int next[M], n, m;
 9 int a[N], b[M];
10 
11 void get_next(int *next)
12 {
13     int i = 0;
14     int j = -1;
15     next[0] = -1;
16     while (i < m)
17     {
18         if (j == -1 || b[i] == b[j])
19         {
20             i++;
21             j++;
22             next[i] = j;
23         }
24         else
25             j = next[j];
26     }
27 }
28 
29 int main()
30 {
31     int T, i, j;
32     while (scanf("%d", &T) != EOF)
33     {
34         while (T--)
35         {
36             scanf("%d%d", &n, &m);
37             for (i = 0; i < n; i++)
38                 scanf("%d", &a[i]);
39             for (i = 0; i < m; i++)
40                 scanf("%d", &b[i]);
41             get_next(next);
42             i = -1, j = -1;    
43             int ans = -1;
44             while (i <= n && j <= m)
45             {
46                 if (j == -1 || a[i] == b[j])    // 关键！
47                 {
48                     ++i;
49                     ++j;
50                 }
51                 else
52                     j = next[j];
53                 if (j == m)
54                 {
55                    ans = i - m + 1;
56                    break;
57                 }
58             }
59             printf("%d\n", ans);
60         }
61     }
62     return 0;
63 }

 

       


联系
我们