| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14258 | 2024_IDS_Spring_Lab4_Fun With Strings |
|
| 14259 | 2024_IDS_Spring_Lab4_Finding Borders |
|
| 14260 | 2024_IDS_Spring_Lab4_Searching for Strings |
|
Description
You have n strings s1, s2, ..., sn, where the strings are combination of lower case characters. You are going to perform q operations. Each operation is in the following format:
1. E i j: Check if si and sj are identical?
2. C i j: Update si to be the concatenation of si and sj. For example, if si = "star" and sj = "burst", then the concatenation of si and sj will be "starburst".
Input
The first line contains integer n and q.
The following n lines are the strings, with the i-th line containing si.
The following q lines are the queries described in the problem description.
Constraints
- 1 ≤ n, q ≤ 100
- Length sum of all strings ≤ 5000
- Length of each string after concatenation ≤ 5000
Output
For each operation `E i j`, please output 'Y' if si and sj are identical, 'N' otherwise.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A border of a string is a prefix that is also a suffix of the string but not the whole string. For example, the borders of abcababcab are ab and abcab.
Your task is to find all border lengths of a given string.
Input
The only input line has a string of length n consisting of characters a–z.
- 1 ≤ n ≤ 106
Output
Print all border lengths of the string in increasing order.
Remember to print a ‘\n’ at the end of the output.
Do not include any spaces at the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You're given a string N , called the needle, and a string H , called the haystack, both of which contain only lowercase letters `a`…`z`.
Write a program to count the number of distinct permutations of N which appear as a substring of H at least once. Note that N can have anywhere between 1 and |N|! distinct permutations in total – for example, the string `aab` has 3 distinct permutations (`aab`, `aba`, and `baa`).
Input
The first line contains N ( 1 ≤ | N | ≤ 2 * 105 ) , the needle string.
The second line contains H ( 1 ≤ | H | ≤ 2 * 105 ) , the haystack string.
Output
Output consists of one integer, the number of distinct permutations of N which appear as a substring of H .
Remember to print a ‘\n’ at the end of the output.