Xâu con
Xem dạng PDF
Gửi bài giải
Điểm:
0,09 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho xâu ~A~ và xâu ~B~ chỉ gồm các chữ cái thường. Xâu ~B~ được gọi là xuất hiện tại vị trí ~i~ của xâu ~A~ nếu: ~A_{i} = B_1~, ~A_{i+1} = B_2~, ..., ~A_{i+length( B )-1} = B_{length( B )}~.
Hãy tìm tất cả các vị trí mà ~B~ xuất hiện trong ~A~.
Input
- Dòng ~1~: xâu ~A~.
- Dòng ~2~: xâu ~B~.
Độ dài ~A~, ~B~ không quá ~1000000~.
Output
- Ghi ra các vị trí tìm được trên ~1~ dòng (thứ tự tăng dần). Nếu ~B~ không xuất hiện trong ~A~ thì bỏ trắng.
Sample Input
aaaaa
aa
Sample Output
1 2 3 4
Bình luận
include <bits/stdc++.h>
define ll long long
using namespace std; ll hashT[1000005],poww[1000005]; string p,t; ll gethash(ll i,ll j) { return hashT[j]-hashT[i-1]poww[j-i+1]; } int main() { cin>>t>>p; ll hashP=0; for(ll i=0;i<p.size();i++) hashP=((hashP26)+p[i]); poww[0]=1; hashT[0]=0; for(ll i=1;i<=t.size();i++){ poww[i]=(poww[i-1]26); hashT[i]=(hashT[i-1]26)+t[i-1]; } for(ll i=1;i<=t.size()-p.size()+1;i++) if(gethash(i,i+p.size()-1)==hashP)cout<<i<<" "; return 0; }
Code Automaton: https://www.ideone.com/lKVhGl
Code c++ nhe moi nguoi :(Hoi Kho):
include <bits/stdc++.h>
using namespace std;
int main() { ios::syncwithstdio(false); cin.tie(nullptr);
}
hàm z hoặc kmp nó y hệt
best with Z algo
Thấy cmt chưa có Z nên mình góp cho vui hihi
mn tham khao : https://ideone.com/C0VlS7
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
test cuối lấy sao vậy ạ mình bị TLE rồi :<
Test cuối bị "khó" đó bạn :D . Hint:
dung KMP.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Nếu dùng thuật Hash các bạn chú ý để long long nhé. Base cũng không nên quá lớn
Hash thì để mod vừa phải và int cũng được để buff tốc độ chạy mặc dù không quá nhiều :D
Tại sao vậy bạn
Bởi trường hợp xấu nhất việc lấy mã hash có thể tràn số do vượt quá kiểu int :/
Base không nên quá lớn cũng vì lý do này (theo kinh nghiệm của mình) :D
Thế tràn bộ nhớ thì sao bạn
với cả base không lớn thì sai số á :((
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.