A. Tìm xâu
Cho 2 xâu A, B độ dài không vượt quá ~10^6~. Đưa ra những vị trí xuất hiện xâu A trong xâu B.
Input
Dòng đầu chứa xâu A
Dòng hai chứa xâu B
Output
Dòng đầu chứa số k là số vị trí xuất hiện xâu A trong xâu B.
Dòng 2 chứa k số nguyên tăng dần xác định k vị trí xuất hiện A trong B
Example
Input
viet
vietnamnamvietviet
Output
3
1 11 15
Hướng dẫn
Hoàn toàn có thể làm trâu bài toán này với độ phức tạp ~O(n*m)~ cùng hàm ~find()~ trong thư viện
Tuy nhiên với thuật toán Hash String thì chỉ cần khởi tạo mã Hash trong ~O(m+n)~ và kiểm tra trong thời gian tuyến tính
Code
#include <bits/stdc++.h>
#define Task ""
#define up(i,a,b) for (int i = (a); i <= (b); i++)
#define base 311
using namespace std;
const int maxn = 10000001;
const int MOD = 1e9 + 7;
const long long MM = 1ll*MOD*MOD;
long long H[maxn];
long long B[maxn];
string a,b;
int n,m;
long long gethash(int u, int v){
return (B[v] - B[u-1]*H[n] + MM) % MOD;
}
signed main (){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> b >> a;
n = a.size();
m = b.size();
a = '@' + a;
b = '@' + b;
long long hashA = 0;
for (int i = 1; i <= n; i++){
hashA = (hashA*base + a[i]) % MOD;
} // Hash code of string a
H[0] = 1;
for (int i = 1; i <= m; i++){
B[i] = (B[i-1]*base + b[i]) % MOD;
// Hash code of substrings from 1 to i in b
H[i] = (H[i-1]*base) % MOD;
// Decryptor
}
for (int v = n; v <= m; v++){
int u = v - n + 1;
if (gethash(u, v) == hashA){
cout << u << " ";
}
}
return 0;
}
Bình luận