Log files | Practice Problems

Log files

★★★★★

2.8

5 votes

String Algorithms, Algorithms, Hashing algorithm, Hashing Algorithm

Details

Submissions

Discussion

Editorial

Problem

You are given a log file in the form of a single string $S$ of length $N$ . You are also given $Q$ queries. There are two types of queries:

You are given a string $W$ . Therefore, perform a substring search for string $W$ in the log file and print the count of occurrences for this string in the file.
You are given $L$ , $R$ , and a string $W$ of length $R-L+1$ . Update the log string indexed from $L$ to $R$ to string $W$ .

Input format

The first line contains two integers $N$ and $Q$ .
The second line contains a string $S$ .
Next $Q$ lines contain one of the two queries mentioned in the problem statement.
- For the first type of query, you will be given $1\ W$ .
- For the second type of query, you will be given $2\ L\ R\ W$ .

Output format

For the query of type 1, you are required to print the count of occurrences of string $S$ in a new line.4.

Constraints

$1 \le N,Q \le 10^5\\ 1 \le L\le R \le N\\ |W| \le N\\ S\ contains\ lower\ case\ alphabets\\ Sum\ of\ lengths\ of\ W \le 10^5$

Time Limit: 3

Memory Limit: 512

Source Limit:

Explanation

Log String = abbabababa
"bab" string matches with [3,5] , [5,7] , [7,9] substrings of original log string.

After second type of query , Log String = ababaababa
"bab" string matches with [2,4] , [7,9] substrings of log string.