hdu1686
可以重叠
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define lson l, m, rt<<111 #define rson m+1, r, rt<<1|112 #define IO ios::sync_with_stdio(false);cin.tie(0);13 #define INF 1e914 #define MAXN 50001015 const int MOD=1e9+7;16 typedef long long ll;17 using namespace std;18 int n, Next[10010], cnt;19 char s[1000010], p[10010];20 void cal_Next()21 {22 int k = -1, len = strlen(p);23 Next[0] = -1;24 for(int i = 1; i < len; i++){25 while(k > -1&&p[k+1] != p[i]){26 k = Next[k];//核心 27 }28 if(p[k+1] == p[i])29 k = k+1;30 Next[i] = k; 31 }32 /*for(int i = 0; i < len; i++){33 cout << Next[i] << " ";34 }*/35 }36 void KMP()37 {38 int k = -1, slen = strlen(s), plen = strlen(p);39 cal_Next();40 for(int i = 0; i < slen; i++){41 while(k > -1&&p[k+1] != s[i]){42 k = Next[k];43 }44 if(p[k+1] == s[i])45 k = k+1;46 if(k == plen-1){47 k = Next[k];//可以重叠 48 cnt++; 49 }50 }51 } 52 int main()53 {54 IO;55 cin >> n;56 while(n--){57 cnt=0;58 cin >> p >> s;59 KMP();60 cout << cnt << endl;61 }62 return 0;63 }
hdu2087
不能重叠
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define lson l, m, rt<<111 #define rson m+1, r, rt<<1|112 #define IO ios::sync_with_stdio(false);cin.tie(0);13 #define INF 1e914 #define MAXN 50001015 const int MOD=1e9+7;16 typedef long long ll;17 using namespace std;18 int n, Next[10010], cnt;19 char s[1000010], p[10010];20 void cal_Next()21 {22 int k = -1, len = strlen(p);23 Next[0] = -1;24 for(int i = 1; i < len; i++){25 while(k > -1&&p[k+1] != p[i]){26 k = Next[k];//核心 27 }28 if(p[k+1] == p[i])29 k = k+1;30 Next[i] = k; 31 }32 /*for(int i = 0; i < len; i++){33 cout << Next[i] << " ";34 }*/35 }36 void KMP()37 {38 int k = -1, slen = strlen(s), plen = strlen(p);39 cal_Next();40 for(int i = 0; i < slen; i++){41 while(k > -1&&p[k+1] != s[i]){42 k = Next[k];43 }44 if(p[k+1] == s[i])45 k = k+1;46 if(k == plen-1){47 k = -1;//不重叠 48 cnt++; 49 }50 }51 } 52 int main()53 {54 IO;55 while(cin >> s){56 if(s[0] == '#')57 break;58 cin >> p;59 cnt=0;60 KMP();61 cout << cnt << endl;62 }63 return 0;64 }