from collections import defaultdict graph=defaultdict(list) v,e=map(int,input().split()) for i in range(e): u,v=map(str,input().split()) graph[u].append(v) graph[v].append(u) for i in graph: print(i,"->",graph[i]) Input: 7 9 A B A C A F C E C F C D D E D G G F Output: F -> ['A', 'C', 'G'] C -> ['A', 'E', 'F', 'D'] G -> ['D', 'F'] D -> ['C', 'E', 'G'] A -> ['B', 'C', 'F'] E -> ['C', 'D'] B -> ['A']
Given an input string and a substring. Find the frequency of occurrences of a substring in a given string.
Input : man (pattern) dhimanman (string) Output : 2
Solution:
def lpsarray(pat,m,lps):
l=0
i=1
lps[0]=0
while(i<m):
if pat[i]==pat[l]:
l+=1
lps[i]=l
i+=1
else:
if l!=0:
l=lps[l-1]
else:
lps[i]=0
i+=1
def kmpsearch(pat,txt):
m=len(pat)
n=len(txt)
lps=[None]*m
lpsarray(pat,m,lps)
i=0
j=0
res=0
next_i=0
while(i<n):
if pat[j]==txt[i]:
j=j+1
i+=1
if j==m:
j=lps[j-1]
res+=1
if lps[j]!=0:
next_i+=1
i=next_i
j=0
elif i<n and pat[j]!=txt[i]:
if(j!=0):
j=lps[j-1]
else:
i+=1
return res
txt="aaababbbaaa"
pat="ab"
ans=kmpsearch(pat,txt)
print(ans)
Solution Credit:frequency-substring-string
Comments
Post a Comment