HDU 4749 Parade Show(贪心+kmp)

题目都看不懂，做毛线。。。看懂了之后就是kmp出，所有的匹配区间，然后DP可以写，贪心也可以做把，DP应该需要优化一下，直接贪，也应该对的，经典贪心问题。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int s1[100001],s2[100001];
 8 int p[100001],o[100001];
 9 int next[100001];
10 int flag[100001];
11 int judge(int x,int y)
12 {
13     if(x == y)
14     return 1;
15     else if(x > y)
16     return 0;
17     else
18     return -1;
19 }
20 int main()
21 {
22     int n,m,k,len1,len2,i,j;
23     while(scanf("%d%d%d",&n,&m,&k)!=EOF)
24     {
25         memset(flag,0,sizeof(flag));
26         for(i = 0;i < n;i ++)
27         scanf("%d",&p[i]);
28         for(i = 0;i < m;i ++)
29         scanf("%d",&o[i]);
30         if(m == 1)
31         {
32             printf("%d
",n);
33             continue;
34         }
35         for(i = 0;i < m-1;i ++)
36         s1[i] = judge(o[i+1],o[i]);
37         for(i = 0;i < n-1;i ++)
38         s2[i] = judge(p[i+1],p[i]);
39         len1 = m-1;//kmp
40         len2 = n-1;
41         next[0] = -1;
42         j = -1;
43         for(i = 1;i < len1;i ++)
44         {
45             while(j >= 0&&s1[j+1] != s1[i])
46             j = next[j];
47             if(s1[j+1] == s1[i]) j ++;
48             next[i] = j;
49         }
50         j = -1;
51         for(i = 0;i < len2;i ++)
52         {
53             while(j >= 0&&s1[j+1] != s2[i])
54             j = next[j];
55             if(s1[j+1] == s2[i])j ++;
56             if(j == len1-1)
57             {
58                 flag[i-len1+1] = 1;
59                 j = next[j];
60             }
61         }
62         int ans = 0;
63         for(i = 0;i < n-1;i ++)
64         {
65             if(flag[i])
66             {
67                 ans ++;
68                 i = i + m - 1;
69             }
70         }
71         printf("%d
",ans);
72     }
73     return 0;
74 }