16,000,841 members
See more:
```Given a pattern p to be a string, and the target string target, output the total number of patterns in the target string target
p will only be number characters and target will only be lower case characters
Runtime: 5s
Test case:
2≤ 𝑙𝑒𝑛(𝑝)≤10^2
1≤𝑙𝑒𝑛(𝑡𝑎𝑟𝑔𝑒𝑡)≤10^9

Example 1
Input: '112', 'kehaanggrrd'
Output: 3
p: 112
target: kehaanggrrd

the pattern '112' appears 3 times in the target string kehaanggrrd, which includes 'aan', 'ggr' and 'rrd'

Example 2
Input: '7227', 'abbccb'
Output: 1

p: 7227
target: abbccb

the pattern '7227' appears 1 times in the target string abbccb, which includes 'bccb

What I have tried:

i am a ngreen in python, our mentor give a assignment and i have not idea about how to solve the problem, Thanks for your help!!!```
Posted
Updated 21-Sep-23 21:44pm
Dave Kreskowiak 22-Sep-23 9:59am

## Solution 1

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, this is part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]

## Solution 2

Lots of information at The Python Tutorial — Python 3.10.12 documentation[^]. Or if you really do not understand the question then ask your mentor.

## Solution 3

Python
```def compute_next(pattern: str) -> list:
"""
Compute the 'next' array for the KMP algorithm.

Args:
pattern (str): The pattern (substring) for which to compute the 'next' array.

Returns:
list: The computed 'next' array.
"""
next: list = [0] * len(pattern)
j: int = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = next[j - 1]
if pattern[i] == pattern[j]:
j += 1
next[i] = j
return next

def kmp(text: str, pattern: str) -> int:
"""
Perform the Knuth-Morris-Pratt (KMP) string matching algorithm.

Args:
text (str): The input text in which to search for the pattern.
pattern (str): The substring to search for in the text.

Returns:
int: The total number of occurrences of the pattern in the text.
"""
next = compute_next(pattern)
count = 0
j = 0
for i in range(len(text)):
dic = {}
dic[pattern[j]] = text[i]
while j > 0 and text[i] != dic[pattern[j]]:
j = next[j - 1]
if text[i] == dic[pattern[j]]:
j += 1
if j == len(pattern):
count += 1
j = next[j - 1]
return count```

if you need to run,simply call the KMP function, and the function will return the final count.

Richard MacCutchan 7-Oct-23 11:09am
You do not help people by doing their homework for them.
[no name] 8-Oct-23 13:39pm
Thank you for your response. This question was asked by a friend of mine. It's a homework assignment for their data structures class. After completing this question, I found it quite challenging for some undergraduate students who haven't studied the KMP algorithm thoroughly. Also, I couldn't find any answers to this question online. In fact, rather than providing the code directly, I would prefer to teach everyone how to solve this question. I will make sure to keep that in mind for future responses.
The next time I have some free time, I will revise my response. I will transform my response into a more detailed explanation of the problem, rather than just providing code.
Richard MacCutchan 9-Oct-23 4:04am
The point I was trying to make is that homework type assignments have a specific reason for being posed. They are designed to make the pupil learn to think for themselves, and try different approaches to find a good solution. When someone hands them a complete solution they have no need to think for themselves. So such people can end up getting through their education without too much trouble, but once they hit the workplace they will be totally exposed.

I know that is an extreme example, but I have worked with such people, and know what a drag they are on the rest of the team.
li wilde 22-Oct-23 9:24am
wow? thanks for your answering, although I've addressed the question, do we know each other? Are you my senior?

Top Experts
Last 24hrsThis month
 OriginalGriff 60 Dave Kreskowiak 55 Christian Graus 40 honey the codewitch 25 Daniel Pfeffer 20
 OriginalGriff 631 Dave Kreskowiak 276 Pete O'Hanlon 260 Richard Deeming 245 CPallini 120

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900