{"code":"20thtc1","name":"Xâu tương đồng (Tin học trẻ C - Vòng Toàn quốc 2020)","description":"Cho 2 xâu $A$ và $B$ chỉ chứa các kí tự in hoa trong khoảng từ `A` tới `Z`. Kí hiệu $|A|$, $|B|$ lần lượt là độ dài của hai xâu $A$ và $B$, ($1 \\le |A|,|B| \\le 50000$). Các kí tự của mỗi xâu được đánh số từ $1$.\r\n\r\nGọi $A[i..j]$ là xâu con gồm các kí tự liên tiếp của xâu $A$ từ vị trí thứ $i$ đến vị trí thứ $j$ ($1 \\le i \\le j \\le |A|$). Gọi $B[p..q]$ là xâu con gồm các kí tự liên tiếp của xâu $B$ từ vị trí thứ $p$ đến vị trí $q$ ($1 \\le p \\le q \\le |B|$).\r\n\r\nHai xâu con $A[i..j]$ và $B[p..q]$ được gọi là tương đồng nhau nếu tập hợp các chữ cái xuất hiện trong xâu con $A[i..j]$ bằng với tập hợp các chữ cái xuất hiện trong xâu con $B[p..q]$.\r\n\r\nXét ví dụ $A=$ `AAABBC` và $B=$ `AZACAB` ta có:\r\n\r\n$A[3..5]=$ `AAB` và $B[5..6]=$ `AB` là tương đồng nhau vì có cùng tập hợp các chữ cái xuất hiện là {`A`,`B`}.\r\n$A[3..6]=$ `ABBC` và $B[4..6]=$ `CAB` là tương đồng nhau vì có cùng tập hợp các chữ cái xuất hiện là {`A`,`B`,`C`}.\r\n\r\n**Yêu cầu:** cho xâu $A$ và xâu $B$, hãy xác định số bộ $(i,j,p,q)$ ($1 \\le i \\le j \\le |A|, 1 \\le p \\le q \\le |B|$) thỏa mãn $A[i..j]$ tương đồng với $B[p..q]$.\r\n\r\n#### Input\r\n\r\n - Dòng thứ nhất ghi xâu $A$.\r\n - Dòng thứ hai ghi xâu $B$.\r\n\r\n#### Output\r\n\r\n - Một số nguyên duy nhất là số lượng bộ $(i,j,p,q)$ thỏa mãn yêu cầu.\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($10\\%$ số điểm): $1 \\le |A|,|B| \\le 10$.\r\n - Subtask $2$ ($20\\%$ số điểm): $1 \\le |A|,|B| \\le 100$.\r\n - Subtask $3$ ($30\\%$ số điểm): $1 \\le |A|,|B| \\le 1000$.\r\n - Subtask $4$ ($40\\%$ số điểm): $1 \\le |A|,|B| \\le 50000$.\r\n\r\n#### Example\r\n\r\n???+ question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        AAABBC\r\n        AZACAB\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        34\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n        - Có $18$ bộ cùng có tập hợp chữ cái là {`A`}.\r\n        - Có $3$ bộ cùng có tập hợp chữ cái là {`B`}.\r\n        - Có $1$ bộ cùng có tập hợp chữ cái là {`C`}.\r\n        - Có $6$ bộ cùng có tập hợp chữ cái là {`A`, `B`}.\r\n        - Có $6$ bộ cùng có tập hợp chữ cái là {`A`, `B`, `C`}.","points":1900.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}