Finding a substring of a string in Python without inbuilt functions [duplicate]

Question

I'm trying to write some code that finds a substring within a string. So far I have this:

main = "dedicated"
sub = "cat"
count = 0
for i in range (0,len(main)):
   match = True
   if sub[0]==main[i]:
     j=0
     for j in range(0,len(sub)):
         if sub[j]!=main[i+j]:
             match = False
             print "No substring"
             break
         else:
             count=count+1
             if match == True and count == len(sub):
                 print "Substring"
                 print "Position start:",i

"dedicate" and "cat" works
"this is an example" and "example" returns an IndexError
"nothing" and "different" returns nothing at all

Can anyone help me/give me pointers/improve the code so that it works correct with the bullet points above?

Do you have a question?

jonrsharpe
– jonrsharpe

2015-10-19 14:47:07 +00:00
Commented Oct 19, 2015 at 14:47 — jonrsharpe
– jonrsharpe, Commented Oct 19, 2015 at 14:47
Can you give more details on the IndexError?

Alex Hall
– Alex Hall

2015-10-19 14:50:02 +00:00
Commented Oct 19, 2015 at 14:50 — Alex Hall
– Alex Hall, Commented Oct 19, 2015 at 14:50
It returns "IndexError: string index out of range"

Sectah
– Sectah

2015-10-19 14:52:43 +00:00
Commented Oct 19, 2015 at 14:52 — Sectah
– Sectah, Commented Oct 19, 2015 at 14:52
Rather sounds like a "question" for code review

m02ph3u5
– m02ph3u5

2015-10-19 14:56:22 +00:00
Commented Oct 19, 2015 at 14:56 — m02ph3u5
– m02ph3u5, Commented Oct 19, 2015 at 14:56
@m02ph3u5 broken code is off-topic there

jonrsharpe
– jonrsharpe

2015-10-19 14:58:23 +00:00
Commented Oct 19, 2015 at 14:58 — jonrsharpe
– jonrsharpe, Commented Oct 19, 2015 at 14:58

inspectorG4dget · Accepted Answer · 2015-10-19 14:53:56Z

6

def index(s, sub):
    start = 0
    end = 0
    while start < len(s):
        if s[start+end] != sub[end]:
            start += 1
            end = 0
            continue
        end += 1
        if end == len(sub):
            return start
    return -1

Output:

>>> index("dedicate", 'cat')
4
>>> index("this is an example", 'example')
11
>>> index('hello world', 'word')
-1

answered Oct 19, 2015 at 14:53

inspectorG4dget

115k30 gold badges159 silver badges253 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ergonaut · Accepted Answer · 2015-10-19 14:58:57Z

0

To fix your issue, add this:

main = "this is an example"
sub = "example"
count = 0
done = False
for i in range (0,len(main)):
   match = True
   if sub[0]==main[i]:
     j=0
     for j in range(0,len(sub)):
         if sub[j]!=main[i+j]:
             match = False
             print "No substring"
             break
         else:
             count=count+1
             if match == True and count == len(sub):
                 print "Substring"
                 print "Position start:",i
                 done = True
                 break
   if done == True:
     break

Notice at the end, you're done.. so then set it to end the program with a variable, and break out of the loop. Then break out of the outer loop.

You do however need to fix the issue where subs may try and exceed the length of main, eg.

main = "this is an example"
sub = "examples"

In which case you need to check if the j iterator is out of range. I will leave that to you to figure out as it was not part of the original question.

edited Oct 19, 2015 at 14:58

answered Oct 19, 2015 at 14:53

ergonaut

7,0671 gold badge21 silver badges50 bronze badges

1 Comment

Sectah Over a year ago

Hey, thanks for the help. However, after trying out a few more different inputs I found that "dedcaicated" and "cat" returns: No substring Substring Position start: 6.

Lucky · Accepted Answer · 2018-11-16 05:53:11Z

0

s1="gabcdfahibdgsabc hi kilg hi"
s2="hi"
count=0
l2=len(s2)
for i in range(len(s1)):
    if s1[i]==s2[0]:   
        end=i+l2
        sub1=s1[i:end]
        if s2==sub1:
            count+=1
print (count)

answered Nov 16, 2018 at 5:53

Lucky

11 bronze badge

Comments

Poonam Adhav · Accepted Answer · 2020-02-13 12:03:50Z

0

def find_sub_str(sample, sub_str):
    count = 0
    for index in range(len(sample)):
        nxt_len = index + len(sub_str)
        if sample[index:nxt_len] == sub_str:
            count += 1
        print("Sub string present {} position start at index 
        {}".format(sample[index:nxt_len], index))
    print("no of times subsring present: ", count)

find_sub_str("dedicate", "cat")
Sub string present cat position start at index 4
no of times subsring present: 1

find_sub_str("nothing", "different")
no of times subsring present: 0

find_sub_str("this is an example", "example")
Sub string present example position start at index 11
no of times subsring present: 1

edited Feb 13, 2020 at 12:03

answered Feb 13, 2020 at 11:56

Poonam Adhav

4124 silver badges10 bronze badges

Comments

Vivek Sable · Accepted Answer · 2020-03-05 12:19:03Z

Consider Following Input

sub_str = "hij"
input_strs = "abcdefghij"

Logic here is -

Check string is sub string or not by group of sequential order of main string start from 0 to end of string.

Iterations are like following - 
Iteration 1:  abc
Iteration 2:  bcd
Iteration 3:  cde
Iteration 4:  def
Iteration 5:  efg
Iteration 6:  fgh
Iteration 7:  ghi
Iteration 8:  hij

Maximum 8 iteration is required when Length of Main string is 8 and Sub string is 3.

Complexity:

Worst case complexity = LenOfMainString - LenOfSubString + 1
Best case complexity = 0 when LenOfSubString is greater than LenOfMainString

Note: This is code to find is given string in present in main string or not i.e. sub-string. Not to get index, but code print index if match else print -1

Code

def is_sub_string(main_str, sub_str):
    """
    @Summary: Check string is sub string of main or not
    @Param main_str(String): Main string in which we have to check sub string is
     present or not.
    @Param sub_str(String): String which we want to check if present in main
     string or not.
    @Return (Boolean): True if present else False.
    """
    # Length of main string and sub string
    # We will iterate over main string is input_str_len - sub_len + 1
    # Means if main string have 10 characters and sub string have 3 characters
    # then in worst case if have to iterate 8 time because last two character
    # can not be sub string, as sub string length is 3
    sub_len = len(sub_str)
    input_str_len = len(main_str)
    index = 0
    is_sub_string = False
    while index<input_str_len-sub_len+1:
        # Check sub_str is equal to sequential group of same characters in main
        # string.
        if sub_str==main_str[index:index+sub_len]:
            is_sub_string = True
            break
        # Increase index count by one to move to next character. 
        index += 1
    print("Total Iteration:", index + 1 if is_sub_string else index, end="\t")
    print("Is Substring:", is_sub_string, end="\t")
    print("Index:",  index if is_sub_string else -1)
    return is_sub_string

Output

Case 01: When string present at start of main string.

status = is_sub_string("abcdefghij", "abc")
>> Total Iteration: 1      Is Substring: True      Index: 0

Case 02: When string present at end of main string.

status = is_sub_string("abcdefghij", "hij")
>> Total Iteration: 8      Is Substring: True      Index: 7

Case 03: When string not present in main string.

status = is_sub_string("abcdefghij", "hix")
>>Total Iteration: 8      Is Substring: False     Index: -1

Case 04: When string length is more than main string.

status = is_sub_string("abcdefghij", "abcdefghijabcdefghij")
>>Total Iteration: 0      Is Substring: False     Index: -1

OR

You can reduce iteration count by half if we search string in starting as well as from ending.

Complexity

Worst case complexity = (LenOfMainString - LenOfSubString + 1)/2
Best case complexity = 0 when LenOfSubString is greater than LenOfMainString

Code

def is_sub_string(main_str, sub_str):
    """
    @Summary: Check string is sub string of main or not
    @Param main_str(String): Main string in which we have to check sub string is
     present or not.
    @Param sub_str(String): String which we want to check if present in main
     string or not.
    @Return (Boolean): True if present else False.
    """
    # Length of main string and sub string
    # We will iterate over main string is (main_str_len - sub_len + 1)/2
    sub_len = len(sub_str)
    input_str_len = len(main_str)
    index = 0
    is_sub_string = False
    find_index = -1
    while index<(input_str_len-sub_len+1)/2:
        # Check sub_str is equal to sequential group of same characters in main
        # string.
        if sub_str==main_str[index:index+sub_len]:
            is_sub_string = True
            find_index = index
            break
        print((index+sub_len)*-1, input_str_len-index, end="\t")
        print(main_str[(index+sub_len)*-1:input_str_len-index], main_str[index:index+sub_len])
        if sub_str==main_str[(index+sub_len)*-1:input_str_len-index]:
            is_sub_string = True
            find_index = (index+sub_len-input_str_len) * (-1)
            break
        # Increase index count by one to move to next characters. 
        index += 1
    print("Total Iteration:", index + 1 if is_sub_string else index, end="\t")
    print("Is Substring:", is_sub_string, end="\t")
    print("Index:",  find_index)
    return is_sub_string

kishandewangan · Accepted Answer · 2020-05-17 05:29:18Z

0

# abcd
# ab
t = int(input())
while t > 0:
    str_Original = input()
    str_Find = input()
    i = 0
    j = 0
    count = 0
    while i < len(str_Original):
        for j in range(len(str_Find)):
            if (len(str_Original) - i - 1) >= j:
                if str_Original[i+j] == str_Find[j]:
                    if j == len(str_Find) - 1:
                        print("Found String at index : " + str(i))
                        count += 1
                else:
                    break
        i += 1
    if count > 0:
        print("Count : " + str(count))
    else:
        print("Did not find any match")
    t -= 1

edited May 17, 2020 at 5:29

answered May 17, 2020 at 5:23

kishandewangan

12 bronze badges

Comments

Samit Saxena · Accepted Answer · 2020-06-25 15:38:58Z

I think the cleanest way to do this is as follows:

string = "samitsaxena"
sub_string = "sa"

sample_list =[]

for i in range(0, len(string)-len(sub_string)+1):
   sample_list.append(string[i:i+len(sub_string)])

print(sample_list)
print(sample_list.count(sub_string))

The output is as follows:

['sa', 'am', 'mi', 'it', 'ts', 'sa', 'ax', 'xe', 'en', 'na']
2

Please observe the sample_list output.

The logic is that we are going to create substrings(from the main string) of length which is equal to the length of the substring.

We are doing this because we want to match these substrings with the given substring.

You can change the values of strings and substrings in code to try out different combinations which would also help you to learn for the code works.

tripleee · Accepted Answer · 2020-10-28 05:26:32Z

0

def count_substring(string, sub_string):
    string = string.lower()
    sub_string = sub_string.lower()

    start = 0
    end = 0

    for index, letter in enumerate(string):
        if letter == sub_string[0]:
            temp_string = string[index:index+len(sub_string)]
            if temp_string == sub_string:
                return index
    return -1

edited Oct 28, 2020 at 5:26

tripleee

192k37 gold badges318 silver badges367 bronze badges

answered Oct 10, 2020 at 9:49

Unknown123

2382 silver badges15 bronze badges

Collectives™ on Stack Overflow

Finding a substring of a string in Python without inbuilt functions [duplicate]

8 Answers 8

Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Linked

Related