Number Sequence HDU - 1711 (kmp模板题)
题意&&思路：
模板题，不再赘述。 匹配数字串，输出最先匹配的一个位置。
AC
#include <iostream>
#include <cstdio>
#define foR(i,x,y) for(int i=(x); i<y; i++)
#define For(i,x,y) for(int i=(x); i<=(y); i++)
using namespace std
;
const int maxn
=1e6+10;
const int maxm
=1e4+10;
int s
[maxn
],p
[maxm
];
int n
,m
,nxt
[maxm
];
void getnxt(int *p
){
int i
=0,j
=-1;
nxt
[0]=-1;
while(i
<m
){
if(j
==-1||p
[i
]==p
[j
])nxt
[++i
]=++j
;
else j
=nxt
[j
];
}
}
int kmp(){
int i
=0, j
=0;
while(i
<n
){
if(j
==-1||s
[i
]==p
[j
])i
++,j
++;
else j
=nxt
[j
];
if(j
==m
)return i
-m
+1;
}
return -1;
}
int main()
{
ios
::sync_with_stdio(0);cin
.tie(0);cout
.tie(0);
int tt
;cin
>>tt
;
while(tt
--){
cin
>>n
>>m
;
foR(i
,0,n
)cin
>>s
[i
];
foR(i
,0,m
)cin
>>p
[i
];
getnxt(p
);
cout
<<kmp()<<endl
;
}
return 0;
}
