KHOPXAU - Khớp xâu
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
0.1s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho hai xâu ký tự ~s~ và ~t~ có độ dài lần lượt là ~n~ và ~m\ (m ≤ n)~. Xâu ~t~ được gọi là xuất hiện (khớp) tại vị trí ~i~ của xâu ~s~ nếu ~t = s[i..(i + m – 1)]~ (hay ~s[i] = t[1], ..., s[i + m – 1] = t[m]~).
Bạn được cho hai xâu ký tự ~s~ và ~t~ chỉ gồm các chữ cái Latinh thường (‘a’, …, ’z’). hãy liệt kê tất cả các vị trí trên xâu ~s~ mà xâu ~t~ xuất hiện.
Input
- Dòng đầu chứa xâu ~s~;
- Dòng thứ hai chứa xâu ~t~.
Giới hạn:
- ~1 ≤ |s|, |t| ≤ 10^6; |t| ≤ |s|~.
Output
- Ghi trên một dòng các vị trí xuất hiện của xâu ~t~ trong xâu ~s~ (chỉ số của ký tự đầu tiên trong xâu là ~1~, các vị trí được liệt kê theo thứ tự tăng dần, hai số liên tiếp được ghi cách nhau một dấu cách).
Sample
Input #1
abababa
ba
Output #1
2 4 6
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
using namespace std;
int main() { iosbase::syncwith_stdio(false); cin.tie(0); cout.tie(0); string s, t; cin >> s >> t; int n = s.length(); int m = t.length(); for (int i = 0; i <= n - m; i++) { if (s.substr(i, m) == t) { cout << i + 1 << " "; } } return 0; }
include <bits/stdc++.h>
using namespace std;
vector<int> build_lps(const string &p) { int m = p.size(); vector<int> lps(m); lps[0] = 0; int len = 0; for (int i = 1; i < m; ) { if (p[i] == p[len]) { lps[i++] = ++len; } else if (len) { len = lps[len - 1]; } else { lps[i++] = 0; } } return lps; }
vector<int> kmpsearch(const string &s, const string &p) { int n = s.size(), m = p.size(); vector<int> res; if (m > n) return res; auto lps = buildlps(p); int i = 0, j = 0; while (i < n) { if (s[i] == p[j]) { i++; j++; if (j == m) { // match ends at i-1, starts at i-m (0-based) res.push_back(i - m + 1); // convert to 1-based index j = lps[j - 1]; } } else if (j) { j = lps[j - 1]; } else { i++; } } return res; }
int main() { ios::syncwithstdio(false); cin.tie(nullptr);
}
Ai có bài giải cho mình tham khảo với