Tách Từ - VNOJ: VNOI Online Judge

Trang chủ » Tách Từ » Tách Từ - VNOJ: VNOI Online Judge

Có thể bạn quan tâm

VI EN Đăng nhập hoặc Đăng ký

Tách từ

Xem dạng PDF Gửi bài giải Danh sách bài nộp Bài nộp tốt nhất Đọc lời giải Điểm: 0,33 (OI) Giới hạn thời gian: 1.0s Giới hạn bộ nhớ: 512M Input: stdin Output: stdout Nguồn bài: Croatian OI 2006 Dạng bài Trie Ngôn ngữ cho phép C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một từ cần được tách thành các đoạn con sao cho mỗi đoạn con thuộc một tập các từ cho trước.

Viết chương trình xác định số cách tách một từ cho trước.

Do kết quả có thể có giá trị lớn, chỉ cần in ra phần dư của kết quả cho ~1337377~.

Input

  • Dòng đầu tiên chứa một từ với tối đa ~300000~ ký tự.
  • Dòng thứ hai chứa số nguyên ~N~, ~1\leq N \leq 4000~.
  • Mỗi dòng trong số ~N~ dòng tiếp theo chứa một từ trong tập các từ. Mỗi từ có độ dài không quá ~100~ ký tự. Không có hai từ nào giống nhau. Tất cả các ký tự đều là chữ cái Latin in thường.

Output

  • In ra một số nguyên duy nhất là phần dư của số cách tách từ khi chia cho ~1337377~.

Sample Input 1

abcd 4 a b cd ab

Sample Output 1

2

Sample Input 2

afrikapaprika 4 afr ika pap r

Sample Output 2

1

Sample Input 3

ababababababababababababababababababababab 3 a b ab

Sample Output 3

759775

Bình luận

Hãy đọc nội quy trước khi bình luận.
  • 3 hieuhfgr đã bình luận lúc 18, Tháng 6, 2024, 6:48 ← chỉnh sửa →

    Hint

    Nếu ta gọi ~cnt_i~ là số cách tách xâu con ~s~ từ ~1 -> i~.

    Tạo Trie cho dãy ~a~.

    Solution:

    (~s~ là xâu từ trong đề bài). Gọi ~cnt_i~ là số cách tách xâu ~s[1..i]~ mà mỗi xâu con đều ở trong tập các từ cho trước. Kết quả của ta là ~cnt_n~ Dễ thấy, ~cnt_i~ sẽ được tính bằng tổng các ~cnt_j~ với ~j~ ~(0 \le j < i)~ là vị trí mà xâu con ~s[j+1..i]~ nằm trong tập các từ. Vì tập các từ có độ dài không vượt quá 100 nên ta có thể for các vị trí ~i~ và for ~j~ mà vẫn đảm bảo độ phức tạp. Việc của chúng ta là cài Trie sao cho tối ưu thoai :3

    lần đầu viết sol mong mọi ng đừng downvote T_T

  • 9 thangdz đã bình luận lúc 11, Tháng 1, 2022, 14:35

    very interesting

Từ khóa » Tách Từ