271D - Good Substrings - CodeForces Solution

data structures strings *1800

Please click on ads to support us..

Python Code: 




import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


def solve(S, B, K):
    MOD = (1 << 50) + 9
    s = set()

    N = len(S)
    pow = [1 for _ in range(N+1)]
    for i in range(1, N+1):
        pow[i] = pow[i-1] * 26
        pow[i] %= MOD
        for i in range(N-1, -1, -1):
        k, h = 0, 0
        for j in range(i, -1, -1):
            ch = S[j]
            if B[ch]:
                k += 1
            if k > K:
                                break
            h += (ord(ch) - ord('a') + 1) * pow[i-j]
            h %= MOD
                        s.add(h)
        return len(s)


S = input()
B = list(input())
K = int(input())

B = {chr(ord('a') + i): False if B[i] == '1' else True for i in range(26)}
print(solve(S, B, K))

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;

char s[2000], che[30];
pair<ULL, ULL> a[2260000];

int main()
{
    scanf("%s%s", s, che);
    int n = 0, k;
    scanf("%d", &k);
    for (int i = 0; s[i]; i++)
    {
        int cnt = 0;
        ULL h1 = 5381, h2 = 0;
        for (int j = i; s[j]; j++)
        {
            if (che[s[j] - 'a'] == '0')
                cnt++;
            if (cnt > k)
                break;
            h1 = h1 * 33ll + s[j];
            h2 = h2 * 131ll + s[j];
            a[n++] = make_pair(h1, h2);
        }
    }
    sort(a, a + n);
    printf("%d\n", (int)(unique(a, a + n) - a));
}


Comments

Submit
0 Comments
More Questions

1306. Jump Game III
236. Lowest Common Ancestor of a Binary Tree
790. Domino and Tromino Tiling
878. Nth Magical Number
2099. Find Subsequence of Length K With the Largest Sum
1608A - Find Array
416. Partition Equal Subset Sum
1446. Consecutive Characters
1618A - Polycarp and Sums of Subsequences
1618B - Missing Bigram
938. Range Sum of BST
147. Insertion Sort List
310. Minimum Height Trees
2110. Number of Smooth Descent Periods of a Stock
2109. Adding Spaces to a String
2108. Find First Palindromic String in the Array
394. Decode String
902. Numbers At Most N Given Digit Set
221. Maximal Square
1200. Minimum Absolute Difference
1619B - Squares and Cubes
1619A - Square String
1629B - GCD Arrays
1629A - Download More RAM
1629C - Meximum Array
1629D - Peculiar Movie Preferences
1629E - Grid Xor
1629F1 - Game on Sum (Easy Version)
2148. Count Elements With Strictly Smaller and Greater Elements
2149. Rearrange Array Elements by Sign