Algorithm to check if a string is a subsequence of another string but not a subword

Question

I am trying to check if there exists a subsequence of a string s2 that is the string s1. The only caveat is the subsequence of s2 that is s1 cannot be a substring of s2.

Subsequence: abac : bc is a subsequence of the string
abcd : bc is a substring and a subsequence of the string

Examples:
s1 = "devil", s2 = "devilishly" True as devil is a subsequence using the last 'l' before the y to make it not a substring
s1 = "devil", s2 = "devilish" False, as devil is a subsequence but is also a substring of devilish

def isSubsequence(str1,str2): 
    i,j = 0, 0

    while j<len(str1) and i<len(str2): 
        if str1[j] == str2[i]:     
            j = j+1    
        i = i + 1

    return j==len(str(1))

I believe this is how to check if a string1 is a subsequence of string2. However, I am not sure how to add the extra property that string1 is not a subword of string2.

Anyone have any ideas on how to go about doing this.

You should rephrase subsequence and subword. Perhaps define those expressions more algorithmic. You are using those expressions in a not consistent way. Btw. Your example 1 for me seems to be false. devil is a subword of devilishly, according to the definition. — aschoerk
– aschoerk, Commented Sep 16, 2019 at 21:47
I rephrased it to be more clear. Regarding example 1, essentially as long as there is a way to build a subsequence that is not just a substring, then the algorithm should return true — genescuba
– genescuba, Commented Sep 16, 2019 at 21:53

David Eisenstat · Accepted Answer · 2019-09-16 23:00:13Z

2

We can get a more algorithmic solution by modifying your code to track whether the subsequence matched so far will extend to a contiguous subsequence. To wit,

def isNoncontiguousSubsequence(str1, str2):
    if len(str1) <= 1:
        return False
    j = 0
    contiguous = True
    for c in str2:
        if str1[j] == c:
            if j < len(str1) - 1:
                j += 1
            elif contiguous:
                contiguous = False
            else:
                return True
        elif j > 0:
            contiguous = False
    return False

answered Sep 16, 2019 at 23:00

David Eisenstat

65.7k7 gold badges66 silver badges127 bronze badges

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

Comments

ThoG · Accepted Answer · 2019-09-16 22:17:36Z

1

You can construct a regex with greedy wildcards in between d.*e.*v.*i.*l Then check of the size of the match is greater than the length of the word (5 for "devil")

Not so pretty python program:

import re

def issubsequence(str1, str2):    
    regex = ".*".join(list(str1))
    m = re.search(regex,str2)
    return m is not None and len(m.group()) > len(str1)

edited Sep 16, 2019 at 22:17

answered Sep 16, 2019 at 21:46

ThoG

514 bronze badges

3 Comments

genescuba Over a year ago

How can you build a regex for an arbitrary input string

genescuba Over a year ago

The regex solution works, I still wonder if there is a more algorithmic way to do this though?

ThoG Over a year ago

It will be difficult to code up from scratch. Regex is a good way to start and very flexible if you want to add other constraints.

Collectives™ on Stack Overflow

Algorithm to check if a string is a subsequence of another string but not a subword

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related