0

I am trying to find out what would be the time complexity if I m trying to look for a string B in A in Python? I understand its different for Lists/Dictionaries etc. I also know its O(n) for lists. so is it the same for string? Will the complexity be O(len(b)*len(A)?

Here is the problem I am working on: Question :Given two strings A and B, find the minimum number of times A has to be repeated such that B is a sub-string of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab", Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

My code in Python is as follows:

if B in A:
    return 1        

lenB=len(B)
lenA=len(A)
n=lenB+lenA
output=''

while n>1:
    output+=A
    n-=lenA


if B in output[:len(output)-lenA]:
    return (len(output)-lenA)/lenA
elif B in output:
    return len(output)/lenA
else:
    return -1
Jidnyasa Babar
  • 69
  • 4
  • 7
    Possible duplicate of [Complexity of \*in\* operator in Python](https://stackoverflow.com/questions/13884177/complexity-of-in-operator-in-python) – Henry Woody Feb 12 '19 at 07:23
  • 1
    for strings O(n), it's likely implemented with [KMP algorithm](https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm) – Kevin He Feb 13 '19 at 01:03
  • Your matching activity should be possible in O(A+B) time and should require only O(A+B) memory, not O(2B). Using a matching DFA for B, it should be possible to repeatedly feed in A instead of composing a string of B length consisting of repeated instances of A. – le3th4x0rbot Feb 13 '19 at 22:22

0 Answers0