| Time Limit: 5000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
Input
Output
Sample Input
2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1
Sample Output
6 -1
Source
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <vector>#include <list>#include <map>#include <set>#include <deque>#include <queue>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>using namespace std;typedef long long LL;#define CLR(x,y) memset((x),(y),sizeof((x)))#define getint(x) int (x);scanf("%d",&(x))#define get2int(x,y) int (x),(y);scanf("%d%d",&(x),&(y))#define get3int(x,y,z) int (x),(y),(z);scanf("%d%d%d",&(x),&(y),&(z))#define getll(x) LL (x);scanf("%I64d",&(x))#define get2ll(x,y) LL (x),(y);scanf("%I64d%I64d",&(x),&(y))#define get3ll(x,y,z) LL (x),(y),(z);scanf("%I64d%I64d%I64d",&(x),&(y),&(z))#define getdb(x) double (x);scanf("%lf",&(x))#define get2db(x,y) double (x),(y);scanf("%lf%lf",&(x),&(y))#define get3db(x,y,z) double (x),(y),(z);scanf("%lf%lf%lf",&(x),&(y),&(z))#define getint2(x) scanf("%d",&(x))#define get2int2(x,y) scanf("%d%d",&(x),&(y))#define get3int2(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))#define getll2(x) scanf("%I64d",&(x))#define get2ll2(x,y) scanf("%I64d%I64d",&(x),&(y))#define get3ll2(x,y,z) scanf("%I64d%I64d%I64d",&(x),&(y),&(z))#define getdb2(x) scanf("%lf",&(x))#define get2db2(x,y) scanf("%lf%lf",&(x),&(y))#define get3db2(x,y,z) scanf("%lf%lf%lf",&(x),&(y),&(z))#define getstr(str) scanf("%s",str)#define get2str(str1,str2) scanf("%s%s",str1,str2)#define FOR(x,y,z) for(int (x)=(y);(x)<(z);(x)++)#define FORD(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)#define FOR2(x,y,z) for((x)=(y);(x)<(z);(x)++)#define FORD2(x,y,z) for((x)=(y);(x)>=(z);(x)--)const int maxn = 1000000 + 10;const int maxm = 10000 + 10;int T[maxn];int P[maxm];int nextt[maxm];int n,m;void makenext(){ memset(nextt, 0 , sizeof(int)*m); for(int i = 1,j = 0;i < m;){ if(P[i] == P[j]) nextt[i++] = ++j; else if( j > 0) j = nextt[j - 1]; else i++; }}int kmp(){ makenext(); for(int i = 0,j = 0;i < n;){ if(T[i] == P[j]) i++,++j; else if( j > 0 ) j = nextt[j - 1]; else i++; if(j == m) return i - m + 1; } return -1;}int main(){ getint(t); while(t--){ get2int2(n,m); FOR(i,0,n) getint2(T[i]); FOR(i,0,m) getint2(P[i]); printf("%d\n",kmp()); } return 0;} |
[2016-02-04][HDU][1711][Number Sequence]
原文：http://www.cnblogs.com/qhy285571052/p/5180821.html