Say I have the following string: "<hello>something WRONG</hello><hello>something else</hello>"

I am trying to find code that works like the following:

 "<hello>" ~~ 
   something : StringPatternThatDoesntContainString["WRONG"] ~~ 
   "</hello>" :> something]

I'm trying to find all the string between hello tags that don't contain the "WRONG" string.


A solution using regular expression with Negative Lookahead (?!regex) Before the Match:

string = "<hello>something WRONG</hello><hello>something else</hello><hello>WRONG</hello>";

 "<hello>" ~~ st : RegularExpression["(?:(?!WRONG).)*?"] ~~ "</hello>" :> st]
{"something else"}

An alternative solution using pure regexes (should be more efficient):

StringCases[string, RegularExpression["(?ms)<hello>((?:(?!WRONG).)*?)</hello>"] :> "$1"]
{"something else"}

A detailed description of this method can be found here.


Performance comparison of the three methods including the improved solution by march (timings for version 10.4.1 on Win7 x64):

string = "<hello>something WRONG</hello><hello>something</hello><hello>something \
stringBig = StringJoin@ConstantArray[string, 3*^2];

  r1 = StringCases[stringBig, 
    "<hello>" ~~ Shortest[st__] ~~ "</hello>" /; StringFreeQ[st, "WRONG"] :> st]]
  r2 = StringCases[stringBig, 
    "<hello>" ~~ st : RegularExpression["(?:(?!WRONG).)*?"] ~~ "</hello>" :> st]]
  r3 = StringCases[stringBig, 
    RegularExpression["(?ms)<hello>((?:(?!WRONG).)*?)</hello>"] :> "$1"]]
r1 === r2 === r3




As one can see, the StringExpression (~~) solution with Condition (/;) is more than 3 orders of magnitude slower than StringExpression without it. What is unexpected is that pure RegularExpression solution is slower than StringExpression without Condition. This topic was discussed before but an explanation was not found.

And here is the output obtained with the same code using version 8.0.4 on the same machine:





As one can see, there is significant speedup for string pattern with Condition in version 10.4.1 as compared to 8.0.4.

  • $\begingroup$ I see you are timing some string matching operations. I haven't gotten around to that yet. I see that the one using Condition is several orders of magnitude worse than the others, perhaps an indication of slow-down induced by more generalized matching. $\endgroup$ – Mr.Wizard Aug 1 '16 at 12:41
  • $\begingroup$ @Mr.Wizard As I understand, Condition is a top-level Kernel function called from the PCRE library. So the huge slowdown is expected in any case as compared to pure PCRE processing. What I wanted to show in my updated answer is that the situation with version 10.4.1 is much better than it was with version 8.0.4: the former is about 5 times faster (and for larger lists the difference is even higher!). The improvement is seemingly due to more efficient implementation of the callback from PCRE to the Kernel (other timings don't differ so much). $\endgroup$ – Alexey Popkov Aug 1 '16 at 12:49
str = "<hello>something</hello><hello>something</hello><hello>something WRONG</hello>";
 "<hello>" ~~ Shortest[st__] ~~ "</hello>" /; StringFreeQ[st, "WRONG"] :> st]
{"something", "something"}

(With hat tip to Alexey Popkov for adding robustness via Shortest).

  • $\begingroup$ Your current solution fails with for example str = "<hello>something</hello><hello>something2</hello>";. You should replace st__ with Shortest[st__] to avoid this: by default string patterns are greedy (in contrast with the usual patterns). $\endgroup$ – Alexey Popkov Mar 28 '16 at 12:11
  • $\begingroup$ @Alexey. Agreed. I will modify it. $\endgroup$ – march Mar 28 '16 at 15:36
  • $\begingroup$ I have taken the liberty to update the output in your answer (which you forgot to update) and to add more representative str for testing the solution. I hope you don't mind. $\endgroup$ – Alexey Popkov Mar 28 '16 at 16:06
  • $\begingroup$ @AlexeyPopkov. Yeah! No problem. I hadn't had my morning coffee yet. $\endgroup$ – march Mar 28 '16 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.