Đếm Xâu Con Chung - LQDOJ: Le Quy Don Online Judge

Trang chủ » đếm Số Xâu Con » Đếm Xâu Con Chung - LQDOJ: Le Quy Don Online Judge

Có thể bạn quan tâm

Tiếng Việt

Tiếng Việt English

Đăng nhập

Đăng ký

Đếm xâu con chung

Xem PDF Nộp bài Tất cả bài nộp Các bài nộp tốt nhất Tác giả: hhoangcpascal Dạng bài string (chuỗi), dp-general (quy hoạch động cơ bản), dp-count (quy hoạch động đếm) Điểm: 1700 (p) Thời gian: 1.2s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ta gọi xâu \(R\) là xâu con của xâu \(S\) nếu ta có thể thu được xâu \(R\) bằng cách xoá đi một vài kí tự của xâu \(S\) và giữ nguyên thứ tự các kí tự còn lại.

Xâu \(C\) được gọi là xâu con chung của hai xâu \(A\) và \(B\) nếu \(C\) là xâu con của \(A\) và \(C\) là xâu con của \(B\). Đếm số lượng xâu con chung của hai xâu \(A\) và \(B\).

Input

  • Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \leq 40)\).
  • Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(10^3\).

Output

  • Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là số xâu con chung. Vì kết quả có thể rất lớn nên chỉ in kết quả khi lấy dư cho \(20071008\).

Example

Test 1

Input 1 abc ab Output 3

Bình luận (7)

Gần nhất Gần nhất Xa nhất Điểm Tải bình luận...

Từ khóa » đếm Số Xâu Con