F. VIRUS - Virus biến dạng

Hôm qua John đọc được một bài viết về cúm gia cầm, trong đó nói rằng ADN của virus cúm có thể thay đổi tạo ra biến dạng mới. Theo bài viết đó, nếu ADN của virus hiện tại được biểu diễn như là một xâu độ dài chỉ bao gồm các ký tự in thường (từ đến ) thì một biến dạng mới rất nguy hiểm là virus có ADN dạng biểu diễn tương tự như xâu nhưng có đúng ký tự cách nhau đúng vị trí (tức là và ) bị thay bằng ký tự nào đó khác.

Biết được thông tin này John vội vàng cho lấy mẫu phân tích ADN của một con trong đàn gia cầm của mình, biến đổi về dạng biểu diễn qua các ký tự in thường (từ đến ) và kiểm tra xem con gia cầm có bị nhiễm vi rút biến dạng hay không?

Giả sử ADN của con gia cầm được biểu diễn bởi xâu , ADN của virus được biểu diễn bởi xâu . Con gia cầm được xem là nhiễm virus biến dạng nếu tồn tại xâu con của sao cho là biến dạng của .

Dữ liệu vào:

• Dòng đầu tiên chứa xâu độ dài biểu diễn mẫu ADN của con gia cầm John chọn;
• Dòng thứ hai chứa xâu độ dài biểu diễn ADN ban đầu của virus;
• Dòng cuối cùng chứa số nguyên ;

Mỗi xâu đều khác rỗng và có độ dài không quá .

Dữ liệu ra:

• Dòng đầu tiên chứa số nguyên , là số lần xâu biến dạng xuất hiện trong ;
• Dòng thứ hai chứa số nguyên theo thứ tự tăng dần, mỗi số nguyên là điểm đầu trong xuất hiện một biến dạng của .

Ví dụ:

Dữ liệu vào:

abcaaaa
baab
3

Dữ liệu ra:

2
3 4

Dữ liệu vào:

abcaaabcd
aecb
2

Dữ liệu ra:

2
1 6

Giải thích:

• Test : Có hai biến dạng của xâu ="baab" trong xâu là "caaa" và "aaaa".

Giới hạn:

• Có số điểm tương ứng số test có ;
• Có số test khác tương ứng số điểm có ;
• Có số test khác tương ứng với số điểm có .