String Hashing

Cho một xâu và một từ khóa, nhiệm vụ của bạn là đếm số lượng vị trí mà từ khóa xuất hiện trong xâu.

Input

• Dòng đầu vào đầu tiên có một xâu độ dài \(n\) và dòng đầu vào thứ hai có một từ khóa độ dài \(m\). Cả hai đều bao gồm các ký tự a - z.
• \(1 \leq n, m \leq 10^6\)

Output

• In một số nguyên: số lần xuất hiện.

Example

saippuakauppias
pp

2

Cho xâu \(S\) độ dài \(N\), hãy lập trình xác định độ dài lớn nhất có thể của một xâu con xuất hiện từ hai lần trở lên trong \(S\) (hai lần xuất hiện này không được giao nhau). Nói cách khác, tìm số nguyên \(l\) lớn nhất sao cho tồn tại hai số chỉ số \(i_1\) và \(i_2\) thỏa mãn:

• \(1\leq i_1, i_2\leq N-l+1\).
• \(i_1+l\leq i_2\).
• \(S[i_1+j]=S[i_2+j]\) với mọi \(j=0,1,2,...,l-1\).

Nếu không tồn tại số nguyên dương \(l\) thỏa mãn thì in ra \(0\).

Input

• Dòng đầu chứa số nguyên dương \(N\) \((N\leq 5000)\).
• Dòng tiếp theo chứa xâu \(S\) độ dài \(N\) chỉ gồm các chữ cái latin in thường.

Output

In ra độ dài lớn nhất tìm được.

Example

5
ababa

2    

2
xy

0    

13
trangeorange

5    

Bờm là một học sinh chuyên tin. Hôm nay Bờm được thầy dạy về thứ tự từ điển và các bài toán liên quan. Sau một hồi giảng giải và định nghĩa thứ tự từ điển là gì, thầy lấy ngay một ví dụ cho lớp. Thầy viết lên bảng 2 chuỗi kí tự dài ơi là dài, và hỏi cả lớp "Chuỗi thứ nhất có thứ tự từ điển như thế nào đối với chuỗi thứ hai: đứng trước (<), đứng sau (>) hay bằng nhau (=) ???".

Cả lớp thì đang hoang mang, vì cũng chẳng có ai hiểu được định nghĩa "Thứ tự từ điển là gì?" của thầy, nói gì đến việc giải bài tập. Nhưng Bờm thì ngược lại, do đã chuẩn bị và xem bài trước ở nhà nên đã trả lời ngay được câu hỏi của thầy sau khi thấy vừa dứt lời. Bờm ngồi chơi trong lúc mọi người đang thảo luận xôn xao, nên đã tạo thêm một số ví dụ nữa về thứ tự từ điển để có thể hiểu sâu thêm về bài học. Nhìn ngay lên bảng, Bờm phát hiện từ 2 xâu trong ví dụ của thầy, Bờm có thể tự sinh ra rất nhiều ví dụ khác. Cụ thể hơn, Bờm chọn một xâu con trong xâu thứ nhất và một xâu con trong xâu thứ hai, thế là có ngay một cặp xâu để mà so sánh. Xâu con ở đây được hiểu là một dãy các ký tự liên tiếp.

Thế là Bờm liên tục sinh ra các ví dụ và trả lời chúng. Bờm càng làm càng nhạy, và trả lời các câu hỏi về thứ tự từ điển càng nhanh. Đến nỗi trong 1 giây Bờm đã có thể trả lời đến tất cả là \(10^6\) câu hỏi!

Yêu cầu: Cho 2 xâu kí tự \(A\) và \(B\) (chỉ gồm các kí tự từ a đến z) và một danh sách gồm \(Q\) câu hỏi có dạng (\(l, r, u, v\)), với ý nghĩa cần so sánh thứ tự từ điển của xâu con \(A[l…r]\) và \(B[u…v]\) (các kí tự của một xâu được đánh số từ trái qua phải, bắt đầu bằng 1; và ký hiệu \(A[l…r]\) thể hiện xâu con từ kí tự thứ \(l\) đến \(r\) của xâu A).
Bạn hãy viết một chương trình mô tả lại hoạt động trả lời các câu hỏi của Bờm.

Lưu ý
Xâu \(a_1a_2…a_n\) (\(a+i\) là kí tự thứ \(i\) trong xâu \(a\)) có thứ tự từ điển nhỏ hơn xâu \(b_1b_2…b_m\) nếu:

• \(n<m\) và \(a_i=b_i\) với mọi \(i\) (\(1\le i\le n\)) hoặc
• Với \(k\) (\(1\le k\le min(m,n)\)) là giá trị nhỏ nhất thỏa \(a+k \ne b_k\) thì \(a_k<b_k\).
• Hai xâu có thứ tự từ điển bằng nhau nếu không thể xác định được xâu nào có thứ tự từ điển nhỏ hơn.

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(L_A, L_B\) là độ dài của xâu \(A\) và xâu \(B\).
• Dòng thứ hai là xâu \(A\).
• Dòng thứ ba là xâu \(B\).
• Dòng tư là số nguyên dương \(Q\) - số câu hỏi trong danh sách
• \(Q\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương \(l, r\ (1\le l\le r\le L_A), u, v\ (1\le u\le v\le L_B)\) mô tả một câu hỏi cần trả lời.

Output

• Với mỗi truy vấn, in ra 1 ký tự =, > hoặc <. Tất cả các câu trả lời được viết trên một dòng.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(|A|, |B|, Q\le 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): \(|A|, |B|, Q\le 10^6\).

Example

13 14
bomthichdacau
bomthichdabanh
3
1 10 1 10
1 10 1 11
1 11 1 11

=<>

Để quảng bá cho cuộc thi chạy của Hippo Runners Club, các thành viên ban quản trị đã rất đau đầu để suy nghĩ ra một cái tên thực sự đáng chú ý. Sau nhiều tháng tranh luận, mọi người đã đi đến thống nhất các quy tắc sau:

• Tên cuộc thi chỉ có thể bao gồm các kí tự in thường Latin (a..z).
• Cho trước 2 xâu \(A\) và \(B\), tên bắt buộc phải bắt đầu bằng \(A\) và kết thúc bằng \(B\).
• Độ dài của tên không được vượt quá \(|A|+|B|+k\) (với \(|S|\) là độ dài xâu \(S\)).

Ví dụ: Với A = “abc”, B = “cde”, k = 3. Những tên sau được xem là hợp lệ: “abcxyzcde”, “abcde”, … và những tên sau là không hợp lệ “abxcde”, “abczzzzcde”, “thoi bay covid 123”, …

Cho trước một xâu \(S\), hãy tìm xem liệu có tồn tại xâu con \(X\) của \(S\) (các kí tự liên tiếp) mà \(X\) là một cái tên hợp lệ hay không.

Input

• Dòng đầu tiên gồm \(T (1 \leq T \leq 10)\) là số testcase:
• Mỗi testcase bao gồm 4 dòng:
  • Dòng đầu tiên gồm 1 số nguyên \(k\) duy nhất.
  • Ba dòng tiếp theo gồm 3 xâu \(S, A, B\) trên mỗi dòng. \((1 \leq n_S, n_A, n_B, k \leq 10^5\) và \(max(n_A, n_B) \leq n_S)\) với \(n_x\) là độ dài xâu \(x\).

Output

• Gồm \(T\) dòng ứng với mỗi testcase. In ra YES nếu tồn tại, ngược lại in NO.

Example

3
7
thoibaycovid
thoi
covid
9
abcde
abc
cde
1
abcccd
abc
d 

YES
YES
NO

John có một chuỗi \(S\). John được yêu cầu thực hiện hai thao tác sau theo thứ tự trên \(S\):

1. Chọn một vị trí của \(S\), và thay thế bằng bất kỳ ký tự nào John muốn.
2. Dịch chuyển chuỗi \(S\), nghĩa là, John có thể chọn một vị trí \(k\) và dịch chuỗi \(S\) theo vòng tròn sao cho \(k\) trở thành vị trí bắt đầu của chuỗi mới.

John muốn sau khi thực hiện hai phép toán trên, kết quả thu được là một chuỗi cho trước. Bạn hãy giúp John tính số cách biến đổi từ chuỗi \(S\) thành một chuỗi \(T\) cho trước.

Input

• Dữ liệu bao gồm hai chuỗi \(S\) và \(T\) trên một dòng. Mỗi chuỗi bao gồm nhiều nhất 100000 ký tự và chỉ gồm các ký tự in hoa.
• Đảm bảo rằng \(S\) và \(T\) có cùng số ký tự.

Output

• Một số duy nhất là số cách biến đổi từ chuỗi \(S\) thành chuỗi \(T\).

Example

AHYANGYI YANGYIAH

8

VSUMSU MSUMSU

2