[백준] 1593번: 문자 해독

https://www.acmicpc.net/problem/1593

initial

So we are checking 2 counters and seeing if they are exactly the same. But the for loop iterates 1 less than the maximum because the end index of the for loop is exclusive (oops). Also, we will get a index out of range error when we reach the max value of i and when we do i+n so we need to exclude running that statement at the end.

from collections import deque, Counter

n,m = map(int,input().split())
w = str(input().strip())
g = str(input().strip())
check = Counter(w)
start = Counter(g[:n])
ans =0

for i in range(len(g)-len(w)):
    if check == start:
        ans+=1
    start[g[i+n]] += 1
    start[g[i]] -= 1

print(ans)

solution

so fixing the wrong points, we get this sliding window

from collections import Counter

n, m = map(int, input().split())
w = str(input().strip())
g = str(input().strip())
check = Counter(w)
start = Counter(g[:n])
ans = 0

for i in range(len(g) - len(w) + 1):
    if check == start:
        ans += 1
    if i + n < len(g):
        start[g[i + n]] += 1
    start[g[i]] -= 1

print(ans)

5x more efficient using ASCII

We create two arrays, W_count and S_count, with a length of 58 (presumably to handle characters in the ASCII range A-Z). These arrays are initialized to all zeros.

Then for each alphabet, we subtract 65 from the ordinal value of characters (computed using the ord() function) to index arrays. The reason for subtracting 65 is to map the character 'A' (ASCII 65) to index 0 in the arrays. This is done to create a count for each character in the range of 'A' to 'Z'.

In Python, the ord() function returns the Unicode code point (ordinal value) of a character. For the English alphabet, 'A' has an ordinal value of 65, 'B' is 66, and so on.

Subtracting 65 from the ordinal value effectively maps 'A' to index 0, 'B' to index 1, 'C' to index 2, and so on in the arrays.

g, s = map(int, input().split())
W = input()
S = input()

W_count = [0] * 58
S_count = [0] * 58

for i in W:
    W_count[ord(i) - 65] += 1

for i in range(g):
    S_count[ord(S[i]) - 65] += 1

count = 0
if W_count == S_count:
    count += 1

for i in range(s-g):
    
    S_count[ord(S[i]) - 65] -= 1
    S_count[ord(S[i+g]) - 65] += 1

    if W_count == S_count:
        count += 1


print(count)

complexity

The code you provided is used to count the number of times a pattern w appears in a given string g using a sliding window approach. The time complexity of this code can be analyzed as follows:

1. Input Processing: The code first reads integers n and m, a pattern w, and a string g. The time complexity for this part is O(m + n) since it involves reading and processing both the pattern and the string.

2. Counter Initialization: The code initializes two Counter objects, check and start, based on the pattern and the initial substring of the string. The Counter initialization has a time complexity of O(n) for both check and start, where n is the length of the pattern.

3. Sliding Window Loop: The main part of the code is a loop that slides a window of size n through the string g. The loop runs from 0 to len(g) - len(w). In each iteration, the following operations occur:

   • Comparison of the Counter objects check and start. This involves checking if check and start are equal. This comparison has a time complexity of O(n) because it involves iterating over the elements in both check and start.

   • Updating the start Counter by incrementing the count for g[i + n] and decrementing the count for g[i]. These operations have a time complexity of O(1).

4. Printing the Result: Finally, the code prints the value of ans. Printing the result has a time complexity of O(1).

Overall, the most time-consuming part of the code is the sliding window loop, which iterates through the string g. The loop runs for len(g) - len(w) iterations, where each iteration involves a comparison of Counter objects and constant-time updates. Therefore, the time complexity of the loop is approximately O((len(g) - len(w)) * n).

The overall time complexity of the code is O((len(g) - len(w)) n), which depends on the lengths of the string g and the pattern w. In the worst case, when w is not found in g, the loop will run for all possible substrings of g, making the time complexity O((len(g) - len(w)) n).