題意：
K長度的模式串，N長度的主串，求多少個位置能夠匹配。
這里模式串以及主串里的值均為rank，即15567和26678認為是匹配的。
解法：
對于這種rank類，判斷是否相等就是判斷在此數(shù)之前大于這個數(shù)字的數(shù)字個數(shù)、等于這個數(shù)字的數(shù)字個數(shù)以及小于這個數(shù)字的數(shù)字個數(shù)是否均相等。接下來的過程就類似KMP的匹配了。
另外，KMP nxt數(shù)組本質(zhì)是最長后綴=最長前綴，
同時要求后綴不能為整個字符串。好久不寫KMP，竟然犯了個糊涂的事情，nxt數(shù)組里算出來竟然是1,2,3,4.。。無語。
代碼：
1 Source Code
2 Problem: 3167 User: yzhw
3 Memory: 24496K Time: 813MS
4 Language: GCC Result: Accepted
5
6 Source Code
7
8 # include <stdio.h>
9 # include <string.h>
10 # define N 100005
11 # define M 30
12 int n,k,s;
13 int cal1[N][M],cal2[N][M],nxt[N],d1[N],d2[N];
14 int equal(int *e1,int *s1,int *e2,int *s2,int val1,int val2)
15 {
16 if(e1[val1-1]-s1[val1-1]==e2[val2-1]-s2[val2-1]&&
17 (e1[val1]-e1[val1-1])-(s1[val1]-s1[val1-1])==(e2[val2]-e2[val2-1])-(s2[val2]-s2[val2-1])&&
18 (e1[s]-e1[val1])-(s1[s]-s1[val1])==(e2[s]-e2[val2])-(s2[s]-s2[val2]))
19 return 1;
20 else return 0;
21 }
22 int main()
23 {
24 int i,t,j,p,total=0;
25 //freopen("cpattern.9.in","r",stdin);
26 //freopen("ans.txt","w",stdout);
27
28 scanf("%d%d%d",&n,&k,&s);
29 memset(cal1,0,sizeof(cal1));
30 memset(cal2,0,sizeof(cal2));
31 for(i=1;i<=n;i++)
32 {
33 scanf("%d",&t);
34 d2[i]=t;
35 //cal2[i][t]++;
36 for(j=1;j<=s;j++)
37 cal2[i][j]+=cal2[i-1][j];
38 for(j=t;j<=s;j++)
39 cal2[i][j]++;
40
41 }
42 for(i=1;i<=k;i++)
43 {
44 scanf("%d",&t);
45 d1[i]=t;
46 //cal1[i][t]++;
47 for(j=1;j<=s;j++)
48 cal1[i][j]+=cal1[i-1][j];
49 for(j=t;j<=s;j++)
50 cal1[i][j]++;
51 }
52 nxt[1]=0;
53 for(i=2;i<=k;i++)
54 {
55 p=nxt[i-1];
56 while(p&&!equal(cal1[p+1],cal1[0],cal1[i],cal1[i-p-1],d1[p+1],d1[i]))
57 p=nxt[p];
58 if(equal(cal1[p+1],cal1[0],cal1[i],cal1[i-p-1],d1[p+1],d1[i])) nxt[i]=p+1;
59 else nxt[i]=0;
60 }
61 p=0;
62 for(i=1;i<=n;i++)
63 {
64 while(p&&!equal(cal1[p+1],cal1[0],cal2[i],cal2[i-p-1],d1[p+1],d2[i])) p=nxt[p];
65 if(equal(cal1[p+1],cal1[0],cal2[i],cal2[i-p-1],d1[p+1],d2[i])) p++;
66 if(p==k)
67 {
68 total++;
69 p=nxt[p];
70 }
71 }
72 printf("%d\n",total);
73 p=0;
74 for(i=1;i<=n;i++)
75 {
76 while(p&&!equal(cal1[p+1],cal1[0],cal2[i],cal2[i-p-1],d1[p+1],d2[i])) p=nxt[p];
77 if(equal(cal1[p+1],cal1[0],cal2[i],cal2[i-p-1],d1[p+1],d2[i])) p++;
78 if(p==k)
79 {
80 printf("%d\n",i-k+1);
81 p=nxt[p];
82 }
83 }
84 return 0;
85 }
86
87