解题思路：用next数组进行跳转次数统计。
解题代码：
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2015年04月12日 星期日 19时40分52秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 int n ; 28 int t; 29 char str[300000]; 30 int len ; 31 int next[300000]; 32 void get_next() 33 { 34 next[0] = -1; 35 int k = -1; 36 int j =0 ; 37 while(j < len ) 38 { 39 if(k == -1 || str[j] == str[k]) 40 { 41 ++ k ; 42 ++ j ; 43 next[j] = k ; 44 }else{ 45 k = next[k]; 46 } 47 } 48 } 49 int find(int x) 50 { 51 if(x == 0) 52 return 0; 53 return 1+find(next[x]); 54 } 55 int main(){ 56 scanf("%d",&t); 57 while(t--) 58 { 59 scanf("%s",str); 60 len = strlen(str); 61 scanf("%s",&str[len]); 62 len = strlen(str); 63 get_next(); 64 printf("%d ",find(len)); 65 } 66 return 0; 67 }