Find a string

  • + 0 comments
    def count_substring(string, sub_string):
        pointers = {}
        cnt = 0
        for i in range(len(string)):
            toPop = []
            # print(f"{pointers=}")
            for k in pointers:
                # print(f"{i=}, {k=}")
                if pointers[k] == len(sub_string): #matched
                    # print(f"{k=}")
                    cnt += 1
                    # print(f"Inc cnt for {k=}")
                    toPop.append(k)
                elif sub_string[pointers[k]] == string[i]: # in progress
                    pointers[k] += 1
                else: #not matched
                    toPop.append(k)
            for k in toPop: # get rid of the items already matched or not mached and keep the ones in progress
                # print(f"Popping {k=}")
                pointers.pop(k)
            if string[i] == sub_string[0] and (i <= len(string) - len(sub_string)):
                # start a new search
                pointers[str(i)] = 1
                # print("adding", i)
                
        for k in pointers:
            # print(f"final check: {i=}, {k=}")
            if pointers[k] == len(sub_string):
                # print(f"{k=}")
                cnt += 1
                # print(f"Inc cnt for {k=}")
        return cnt
            
    
    if __name__ == '__main__':
        string = input().strip()
        sub_string = input().strip()
        
        count = count_substring(string, sub_string)
        print(count)