?

題目傳送門

1 /* 2 題意：問(wèn)一個(gè)串在另一個(gè)串出現(xiàn)的次數(shù)(可重復(fù)) 3 KMP：模板題 4 */ 5 /************************************************ 6 * Author :Running_Time 7 * Created Time :2015-8-9 19:45:40 8 * File Name :POJ_3461.cpp 9 ************************************************/ 10 11 #include <cstdio> 12 #include <algorithm> 13 #include <iostream> 14 #include <sstream> 15 #include <cstring> 16 #include <cmath> 17 #include <string> 18 #include <vector> 19 #include <queue> 20 #include <deque> 21 #include <stack> 22 #include <list> 23 #include <map> 24 #include <set> 25 #include <bitset> 26 #include <cstdlib> 27 #include <ctime> 28 using namespace std; 29 30 #define lson l, mid, rt << 1 31 #define rson mid + 1, r, rt << 1 | 1 32 typedef long long ll; 33 const int MAXN = 1e6 + 10; 34 const int INF = 0x3f3f3f3f; 35 const int MOD = 1e9 + 7; 36 int nex[MAXN]; 37 char s[MAXN], t[MAXN]; 38 39 void get_nex(int lm) { 40 int i = 0, j = -1; nex[0] = -1; 41 while (i < lm) { 42 if (j == -1 || t[j] == t[i]) { 43 j++; i++; nex[i] = j; 44 } 45 else j = nex[j]; 46 } 47 } 48 49 int KMP(void) { 50 int ln = strlen (s); int lm = strlen (t); 51 get_nex (lm); 52 int i = 0, j = 0; int ans = 0; 53 while (i < ln) { 54 while (j != -1 && t[j] != s[i]) j = nex[j]; 55 j++; i++; 56 if (j >= lm) { 57 ans++; j = nex[j]; 58 } 59 } 60 return ans; 61 } 62 63 int main(void) { //POJ 3461 Oulipo 64 int T; scanf ("%d", &T); 65 while (T--) { 66 scanf ("%s%s", t, s); 67 printf ("%d\n", KMP ()); 68 } 69 70 return 0; 71 } 1 /* 2 題目鏈接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4194 3 給你兩個(gè)字符串A，B，請(qǐng)輸出B字符串在A字符串中出現(xiàn)了幾次(不可重復(fù)) 4 */ 5 /************************************************ 6 * Author :Running_Time 7 * Created Time :2015-8-9 19:45:40 8 * File Name :ZSTU_4194.cpp 9 ************************************************/ 10 11 #include <cstdio> 12 #include <algorithm> 13 #include <iostream> 14 #include <sstream> 15 #include <cstring> 16 #include <cmath> 17 #include <string> 18 #include <vector> 19 #include <queue> 20 #include <deque> 21 #include <stack> 22 #include <list> 23 #include <map> 24 #include <set> 25 #include <bitset> 26 #include <cstdlib> 27 #include <ctime> 28 using namespace std; 29 30 #define lson l, mid, rt << 1 31 #define rson mid + 1, r, rt << 1 | 1 32 typedef long long ll; 33 const int MAXN = 1e6 + 10; 34 const int INF = 0x3f3f3f3f; 35 const int MOD = 1e9 + 7; 36 int nex[MAXN]; 37 char s[MAXN], t[MAXN]; 38 39 void get_nex(int lm) { 40 int i = 0, j = -1; nex[0] = -1; 41 while (i < lm) { 42 if (j == -1 || t[j] == t[i]) { 43 i++; j++; nex[i] = j; 44 } 45 else j = nex[j]; 46 } 47 } 48 49 int KMP(void) { 50 int ln = strlen (s); 51 int lm = strlen (t); 52 get_nex (lm); 53 int i = 0, j = 0; int ans = 0; 54 while (i < ln) { 55 while (j != -1 && s[i] != t[j]) j = nex[j]; 56 i++; j++; 57 if (j == lm) { 58 ans++; j = 0; //改動(dòng)這里就是重新匹配 59 } 60 } 61 return ans; 62 } 63 64 int main(void) { 65 while (scanf ("%s%s", s, t) == 2) { 66 printf ("%d\n", KMP ()); 67 } 68 69 return 0; 70 } 71 72 不可重復(fù)的匹配 不可重復(fù)的匹配

?

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/4717802.html

總結(jié)

以上是生活随笔為你收集整理的KMP POJ 3461 Oulipo的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。