?
http://acm.hdu.edu.cn/showproblem.php?pid=1711
這道題就是一個KMP模板。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 const int maxn = 1000000+5; 6 7 int n,m; 8 9 int next[maxn]; 10 int a[maxn], b[maxn]; 11 12 void get_next() 13 { 14 int i = -1, j = 0; 15 ::next[0] = -1; 16 while (j < m) 17 { 18 if (i == -1 || b[i] == b[j]) 19 ::next[++j] = ++i; 20 else 21 i = ::next[i]; 22 } 23 } 24 25 26 int kmp() 27 { 28 int i = 0, j = 0; 29 while (i < n) 30 { 31 if (j == -1 || a[i] == b[j]) 32 { 33 i++; 34 j++; 35 } 36 else 37 j = ::next[j]; 38 if (j == m) 39 return i; 40 } 41 return -1; 42 } 43 44 int main() 45 { 46 //freopen("D:\\txt.txt", "r", stdin); 47 int t; 48 cin >> t; 49 while (t--) 50 { 51 cin >> n >> m; 52 for (int i = 0; i < n; i++) 53 cin >> a[i]; 54 for (int i = 0; i < m; i++) 55 cin >> b[i]; 56 get_next(); 57 int k=kmp(); 58 if (k!=-1) cout << k-m+1 << endl; 59 else cout << "-1" << endl; 60 } 61 return 0; 62 }
?
)
