Wildcard Pattern Matching in Naive string pattern matching

i'm trying to add wildcard pattern matching in my simple naive string matching algorithm,especially the character "*" which will match one or more characters in my list of characters. I have one wildcard character, "?" , which will match one character, implemented. But i have difficulties implementing the "*" wildcard

First here's my simple algorithm:
pat is a list of character patterns
txt is a list of characters

 def search(pat,txt):
        M = len(pat)
        N = len(txt)
        
        for i in range(N-M+1):
            j=0
            while(j<M):
                if pat[j]=="?":
                    j+=1
                    continue
                if (txt[i+j]!=pat[j]):
                    break
                j+=1
                
    
            if(j==M):
                print("Pattern found at index ",str(i))

txt=["A","A","B","A","A","A","C","A","A","D","A","A","B","A","A","A","B","C","A"]
pat=["A","A","?","C"]
search(pat,txt)
# Pattern found at index  3
# Pattern found at index  14

txt=["A","A","B","A","A","A","C","A","A","D","A","A","B","A","A","A","B","C","A"]
pat=["A","A","B","C"]
search(pat,txt)
# Pattern found at index  14

what i want is this using some examples:

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["d","o","g","*","b","o","t","h"]
search(pat,txt)
# Pattern found at index  5
# Corresponding to ["d","o","g","i","l","o","v","e","b","o","t","h"]

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["i","*"]
search(pat,txt)
# Pattern found at index  8
# Corresponding to ["i","l","o","v","e","b","o","t","h"]

txt=["C","a","t","o","r","d","o","g","i","l","o","v","e","b","o","t","h"]
pat=["*","i"]
search(pat,txt)
# Pattern found at index  0
# Corresponding to ["C","a","t","o","r","d","o","g","i"]

How can i do this? Can someone help me please or atleast guide me to the best solution?

Solution

This exercise is covered in depth at geeksforgeeks and reading that resource carefully is probably your best bet. I'll give a quick TLDR here:

Adding wildcard matching makes your coding task significantly more complicated. Depending on your experience level, it might be pretty hard to wrap your head around.
The basic idea is to build an array dp such that dp[j][k] is True if the first k characters of the pattern form a valid match for the first j characters of the input string, and False otherwise.