top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Python: How do I check if a string is a prefix of any possible other string that matches a given regex.

+4 votes
532 views

Probably I'm turning the use of regular expressions upside down with this question. I don't want to write a regex that matches prefixes of other strings, I know how to do that. I want to generate a regex -- given another regex --, that matches all possible strings that are a prefix of a string that matches the given regex.

E.g. You have the regex ^[a-z]*4R$ then the strings "a", "ab", "A4" "ab4" are prefixes of this regex (because there is a way of adding characters that causes the regex to match), but "4a" or "a44" or not.
How do I programmatically create a regex that matches "a", "ab", "A4", etc.. but not "4a", "a44", etc..

Logically, I'd think it should be possible by running the input string against the state machine that the given regex describes, and if at some point all the input characters are consumed, it's a match. (We don't have to run the regex until the end.) But I cannot find any library that does it...

posted Oct 7, 2014 by anonymous

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button

Similar Questions
0 votes

Given a string S and set of strings U. Find the length of longest prefix of S that can be formed using strings in U.

For example you have following -

S= “absolute”
U={“abs”,”xyz”,”ol”,”te”}

Answer: 5 i.e "absol"

Now the task is to have the algorithm/program for the above problem, please help me with this?

+2 votes

I have a multi-line string and I need to remove the very first line from it. How can I do that? I looked at StringIO but I can't seem to figure out how to properly use it to remove the first line.

–1 vote

Write a C program to check if the given string is repeated substring or not.
ex
1: abcabcabc - yes (as abc is repeated.)
2: abcdabababababab - no

...