1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; string t, p; int nxt[1000 * 2 + 1 + 5]; void getNxt(const string &s) { nxt[0] = 0; for (int i = 1; i < s.length(); i++) { int j = nxt[i - 1]; while (j != 0 && s[j] != s[i]) j = nxt[j - 1]; if (s[j] == s[i]) j++; nxt[i] = j; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); while (cin >> t) { if (t == "#") break; cin >> p; // 计算 t 里面能裁出来多少个 p string s = p + " " + t; getNxt(s); // t 的位置为第 p.length()+2 个字符 int now = p.length() + 1; // t第一个字符在s中的下标 int ans = 0; while (now < s.length()) { if (nxt[now] == p.length()) { ans++; now += p.length(); } else now++; } cout << ans << "\n"; } return 0; }
- 1
信息
- ID
- 685
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 48
- 已通过
- 19
- 上传者