SỞ GIÁO DỤC VÀ ĐÀO TẠO NAM ĐỊNH
TRƯỜNG THPT CHUYÊN LÊ HỒNG PHONG
SÁNG KIẾN DỰ THI CẤP TỈNH
BÁO CÁO SÁNG KIẾN
ỨNG DỤNG MẢNG BĂM (HASH) ĐỂ GIẢI CÁC BÀI
TOÁN VỀ SO KHỚP XÂU (CHUỖI)
Tác giả: Ngô Trung Tưởng
Trình độ chuyên môn: Đại học
Chức vụ: Giáo viên
Nơi công tác: Trường THPT chuyên Lê Hồng Phong
Nam Định, tháng 05 năm 2014
THÔNG TIN CHUNG VỀ SÁNG KIẾN
1. Tên sáng kiến:
ỨNG DỤNG MẢNG BĂM (HASH) ĐỂ GIẢI CÁC BÀI TOÁN VỀ SO KHỚP
XÂU (CHUỖI)
2. Lĩnh vực áp dụng sáng kiến:
Giảng dạy lớp 10, 11 chuyên tin, đội tuyển HSGQG môn tin học
3. Thời gian áp dụng sáng kiến:
Từ năm học 2012-2013 đến nay
4. Tác giả:
Họ và tên: Ngô Trung Tưởng
Năm sinh: 1982
Nơi thường trú: 22/34 Trần Thái Tông, P Thống Nhất, TP Nam Định
Trình độ chuyên môn: Đại học
Chức vụ công tác: Giáo viên
Nơi làm việc: Trường THPT chuyên Lê Hồng Phong
Địa chỉ liên hệ: 22/34 Trần Thái Tông, P Thống Nhất, TP Nam Định
Điện thoại: 0982.209.259
5. Đơn vị áp dụng sáng kiến:
Tên đơn vị: Trường THPT chuyên Lê Hồng Phong
Địa chỉ: 76 Vỵ Xuyên

- Chúng ta cần tìm tất cả các vị trí i thỏa mãn (1≤i≤m-n+1) mà T[i i+n-1]=P[1 n]
b. Mô tả thuật toán
Để đơn giản, giả sử rằng Σ = {a, b,…, z}, nghĩa là Σ chỉ gồm các chữ cái
Latin in thường. Để biểu diễn một xâu, thay vì dùng chữ cái, chúng ta sẽ chuyển
sang biểu diễn số ở hệ 26.
Ví dụ: xâu ‘abcd’ biểu diễn hệ 26: ‘a’*26
3
+ ‘b’*26
2
+ ‘c’*26
1
+ ‘d’*26
0
đổi ra số ở
hệ cơ số 10 tương ứng là: 65*26
3
+66*26
2
+67*26+68= 1188866.
Dễ thấy rằng, muốn so sánh 2 xâu bằng nhau khi và chỉ khi biểu diễn của 2 xâu ở
hệ cơ số 10 giống nhau.
Ví dụ xâu A=B ↔ Mã A = Mã B
Tuy nhiên nếu xâu quá dài thì Mã A, Mã B cũng rất lớn. Chính vì thế, ta lấy mod
cho 1 số base nguyên tố rất lớn nào đó ví dụ 10
9
+7, hay 2.10
9
+11…
A=B


//tinh 26
x
mod base
POW[0]=1;
for (i=1;i<=m;i++)
POW[i] = POW[i-1]*26 % base;
//tinh ma Hash xau s[1 i]
HashT[0]=0;
for(i=1;i<=m;i++)
HashT[i]=(HashT[i-1]*26+T[i])%base;
Để lấy mã Hash của T[i j] ta viết hàm sau:
long long getHash(long i, long j){
return(HashT[j]-HashT[i-1]*POW[j-i+1]+ base*base)%base;
}
Bài toán chính được giải quyết như sau:
for (i=1;i<=m-n+1;i++)
if (getHash(i,i+n-1)==HashP)
cout<<i<<” “;
c. Viết chương trình
Đây là chương trình đầy đủ và đã được chấm thành công trên hệ thống chấm bài
SPOJ
/>Chương trình viết bằng C++
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;
const long long base=1000000000+7;
long long hasha[1000005], hashb,POW[1000005];
string a,b;

if (hashb==gethash(i,i+m-1))
//cout<<i<<" ";
fo<<i<<" ";
//cin.get();
fi.close();
fo.close();
return 0;
}
d. Đánh giá:
Độ phức tạp của thuật toán là O(n + m). Nhưng điều quan trọng là: chúng ta có thể
kiểm tra 2 xâu có giống nhau hay không trong O(1). Đây là điều tạo nên sự linh
động cho thuật toán Hash.
4. Ứng dụng
Bài 1: Tiền tố và hậu tố
/>Xâu a được gọi là tiền tố của xâu b nếu xâu a trùng với phần đầu của xâu b. Ví
dụ pre là tiền tố củaprefix
Xâu a được gọi là hậu tố của xâu b nếu xâu a trùng với phần cuối của xâu b. Ví
dụ fix là hậu tố củasuffix
yenthanh132 vừa mới học về tiền tố và hậu tố nên hôm nay anh ta sẽ đố các bạn
một bài toán đơn giản về tiền tố và hậu tố như sau:
• Cho 2 xâu a,b gồm các kí tự latin thường ('a' đến 'z')
• Tìm 1 xâu c thỏa mãng:
1. Xâu a là tiền tố của xâu c
2. Xâu b là hậu tố của xâu c
3. Độ xài xâu c là ngắn nhất.
Input
• Dòng 1: Xâu a
• Dòng 2: Xâu b
Output
• Một dòng duy nhất là xâu c.

typedef long long ll;
const ll BASE=1000000000+11;
string a,b;
ll ha[100005],hb[100005],POW[100005];
long n,m;
bool kt(long x){
ll xa,xb;
long n=a.size()-1;
xb=hb[x];
xa=(ha[n]-ha[n-x]*POW[x]+BASE*BASE)%BASE;
if (xa==xb) return 1;
else return 0;
}
int main(){
getline(cin,a);
a='@'+a;
getline(cin,b);
b='@'+b;
//tinh ham mu
POW[0]=1;
for (long i=1;i<a.size();i++)
POW[i]=POW[i-1]*26 % BASE;
//tinh hash xau a
ha[0]=0;
for (long i=1;i<a.size();i++)
ha[i]=(ha[i-1]*26+a[i])% BASE;
//tinh hash xau b
hb[0]=0;
for (long i=1;i<b.size();i++)
hb[i]=(hb[i-1]*26+b[i])% BASE;

Example
Input:
3
4
flashmt
ll931110
technolt
tuananhnb93
3
mr_invincible
conankudo
ll931110
3
khanhptnk
hphong
technolt
Output:
8
Hướng dẫn thuật toán:
- Mỗi xâu mã hóa dưới dạng số lưu vào một phần tử của mảng, sắp xếp lại
mảng, đếm số lượng số khác nhau trong mảng.
- Độ phức tạp O(K.N+N logN)
Chương trình C++
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const long long BASE=1000000000+11;
long n,k,m=0;
long long hash;

xuất hiện ít nhất hai lần (xuất hiện trong hai vị trí khác nhau trên trang giấy)?
Yêu cầu: Hãy giúp John trả lời câu hỏi đó.
Dữ liệu vào cho trong tệp SUBSTR.INP
- Dòng 1 chứa số nguyên L (1≤L≤200000) là độ dài mà Jonh đã viết trên giấy.
- Dòng 2 chứa một xâu có độ dài L gồm các kí tự chữ thường trong bảng chữ
cái tiếng anh.
Kết quả ghi ra tệp SUBSTR.OUT một số duy nhất là độ dài dài nhất của xâu xuất
hiện ít nhất hai lần trong xâu đã cho. Nếu không tồn tại xâu con thỏa mãn đưa ra số
0.
SUBSTR.INP SUBSTR.OUT
18
trutrutiktiktappop
4
Hướng dẫn:
- Nhận xét:
+ Nếu tồn tại một xâu con dài nhất độ dài l xuất
hiện ít nhất 2 lần trong xâu s.
+ Tồn tại một xâu con có độ dài l-1 xuất hiện ít
nhất 2 lần trong s và không tồn tại xâu con có độ
dài l+1 thỏa mãn yêu cầu đầu bài.
- Từ nhận xét trên ta sử dụng thuật toán tìm kiếm nhị
phân theo độ dài xâu con cần tìm.
- Mỗi xâu con độ dài l, ta sẽ tính mã hash của tất cả
các xâu con lưu vào mảng.
- Nếu mảng vừa tạo tồn tại ít nhất 2 phần tử giống
nhau tức là tồn tại ít nhất 2 xâu con có độ dài l
thỏa mãn.
- Tìm l có độ dài dài nhất thỏa.
- Độ phức tạp của thuật toán Nlog
2

POW[i]=(POW[i-1]*26) % base;
hash[0]=0;
for (long i=1;i<=n;i++)
hash[i]=(hash[i-1]*26+s[i]-'a')% base;
long l=1,r=n,g;
while (l<r){
g=(l+r+1)/2;
if (kt(g)) l=g;
else r=g-1;
}
if (kt(r)) fo<<r;
else fo<<0;
return 0;
}
Bài 4 - DTKSUB – Tìm chuỗi con dài nhất xuất hiện K lần
/>Sau những kỳ công trong những cuộc chinh phục các cấu trúc dữ liệu đặc biệt,
tình bạn giữa piratevà duyhung123abc ngày càng trở nên khăng khít. Rồi bỗng một
ngày nọ, duyhung123abc bỗng ra đi không một lời từ biệt, chỉ để lại một mẫu giấy
cho pirate. Mẩu giấy viết rằng : "Em ơi, anh còn nặng nợ toán lý hóa anh, chưa thể
một lòng theo đuổi tin học. Em hãy làm nốt công việc mà anh em ta còn dang
dở !". pirate đọc xong, nước mắt giàn giụa. Nếu khi hai người gặp nhau, vui sướng
như khi Engels gặp Marx, thì trong giây phút chia ly này, lòng pirate đau đớn như
khi Đỗ Phủ tiễn người tri kỉ Lý Bạch lên đường.
Mất đi người anh cả, pirate như con thuyền mất phương hướng. Cuối cùng, sau
những đêm không ngủ, anh quyết định rằng mình sẽ đợi cho đến
khi duyhung123abc trả xong nợ công danh và quay trở về sẽ tiếp tục nghiên cứu
các cấu trúc dữ liệu đặc biệt. Còn bây giờ, anh ta sẽ đi một con đường mới, đi vào
một thế giới mới, thế giới của các THUẬT TOÁN VỀ CHUỖI. Tuy cô độc một
mình, nhưng với niềm tin của mình, pirate đã lên đường ngay mà không có chút do
dự.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const long long base=1000000000+7;
long n,k;
char s[50005];
long long hash[50005],POW[50005],a[50005];
long long gethash(long i, long j){
return (hash[j]-hash[i-1]*POW[j-i+1]+
base*base)% base;
}
bool kt(long x){
for (long i=1;i<=n-x+1;i++)
a[i-1]=gethash(i,i+x-1);
sort(a,a+n-x+1);
long count=1,max=1;
for (long i=1;i<n-x+1;i++){
(a[i]==a[i-1])? (count++):(count=1);
if (max<count) max=count;
}
if (max>=k) return 1;
return 0;
}
int main(){
cin>>n>>k;
for (long i=1;i<=n;i++) cin>>s[i];
POW[0]=1;
for (long i=1;i<=n;i++)
POW[i]=(POW[i-1]*26) % base;

hiện trong s và không tồn tại xâu con có độ dài l+2
thỏa mãn yêu cầu đầu bài.
- Từ nhận xét trên ta sử dụng thuật toán tìm kiếm nhị
phân theo độ dài chẵn xâu con cần tìm.
- Tương tự ta xét với độ dài xâu con độ dài lẻ.
- Độ phức tạp của thuật toán Nlog(N)
Chương trình viết bằng C++
#include <iostream>
#include <string>
#include <algorithm>
const long long base=1000000000+7;
using namespace std;
long n,res;
char s[50002],t[50002];
long long hashs[50002],hasht[50002],POW[50002];
long long gethash(long long x[],long a, long b){
return (x[b]-x[a-1]*POW[b-a+1]+base*base)%base;
}
bool ok(long k){
for (long i=1;i<=n-k+1;i++)
if (gethash(hashs,i,i+k-1)==gethash(hasht,n-k-
i+2,n-i+1)) return 1;
return 0;
}
int main(){
cin>>n;
for (long i=1;i<=n;i++){
cin>>s[i];
t[n+1-i]=s[i];
}

}
5. Tổng kết:
a. Thuật toán:
Ý tưởng thuật toán Hash dựa trên việc đổi từ hệ cơ số lớn sang hệ thập phân, so
sánh hai số thập phân lớn bằng cách so sánh phần dư của chúng với một số đủ lớn.
b. Ưu điểm:
Ưu điểm của thuật toán Hash là cài đặt rất dễ dàng. Linh động trong ứng dụng và có
thể thay thế các thuật toán chuẩn ‘hầm hố’ khác.
c. Nhược điểm:
Nhược điểm của thuật toán Hash là tính chính xác. Mặc dù rất khó sinh test để có
thể làm cho thuật toán chạy sai, nhưng không phải là không thể. Vì vậy, để nâng
cao tính chính xác của thuật toán, người ta thường dùng nhiều modulo khác nhau để
so sánh mã Hash (ví dụ như dùng 3 modulo một lúc).