Contest Edu #1 - Xâu ưng ý

View as PDF

Submit solution

Points: 0.50
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho hai xâu ~A~ độ dài ~N~ và ~B~ độ dài ~M~.

Đối với mỗi chữ cái ~c\in['a'...'z']~, ~D_c~ được gọi là giá trị của chữ cái ~c~. Gọi độ ưng ý của 2 xâu ~A~ và ~B~ là số ~l~ lớn nhất sao cho tồn tại hai vị trí ~i,j~ thỏa mãn đẳng thức sau: $$ {\frac{D_{A_i}}{D_{B_j}} = \frac{D_{A_i} + D_{A_{i+1}}}{D_{B_j} + D_{B_{j+1}}} = \frac{D_{A_i} + D_{A_{i+1}} + D_{A_{i+2}}}{D_{B_j} + D_{B_{j+1}} + D_{B_{j+2}}} = \cdots = \frac{{\sum\nolimits_{x=0}^{l-1}} D_{A_{i+x}}}{{\sum\nolimits_{x=0}^{l-1}} D_{B_{j+x}}}} $$

Yêu cầu

Cho hai xâu ~A~ và ~B~ và mảng ~D~, hãy xác định độ ưng ý của nó.

Dữ liệu

  • Dòng đầu chứa hai số là ~N~ và ~M \ (1 \leq N, M \leq 2 \times 10^5)~.
  • Dòng thứ hai chứa xâu ~A~ gồm ~N~ ký tự Latin in thường.
  • Dòng thứ hai chứa xâu ~B~ gồm ~M~ ký tự Latin in thường.
  • Dòng thứ tư chứa mảng ~D~ gồm ~26~ số nguyên dương. Số thứ 1 là giá trị của chữ cái ~a~, số thứ 2 là giá trị của chữ cái ~b~,... ~(D_i \leq 10^9)~.

Kết quả

Gồm 1 số nguyên duy nhất là độ ưng ý của 2 xâu ~A,B~ theo miêu tả đề bài.

Ví dụ

Sample Input
6 7
aabacf
cfcferh
2 1 4 9 16 8 7 24 8 17 30 9 35 9 10 19 26 32 55 36 27 18 20 34 17 40
Sample Output
5
Giải thích

Với ~l~ = ~5~, hai vị trí ~i, j~ lần lượt là 2 và 2.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.