3
$\begingroup$

I want to extract non-overlapping substrings from strings with only four possible characters a,b,c,d. These strings will always have equally many "a" and "d" characters. The substrings x I want satisy the following criteria:

  1. x starts with an "a" and ends with a "d", or is an "isolated" "b" or "c", see below.
  2. x has equally many "a"'s and "d"'s.
  3. Any substring of x starting at the first "a" has more "a"s than, or equally many "a"'s as, "d"'s.

For instance, the substrings I'm looking for in "abdcbaacdabbdd" are:

  • "abd"
  • "c"
  • "b"
  • "aacdabbdd"

I have made a working code doing this iteratively:

pick[i_]:=(Which[
occ[[i]]=="a",If[trigger++==0,startpos=i],
occ[[i]]=="d",If[--trigger==0,Sow[occ[[startpos;;i]]]],
trigger==0,Sow[{occ[[i]]}];
];
i+1);

subStrings[s_String]:=
Block[
{trigger=0,startpos,occ=Characters[s]},
Reap[Nest[pick,1,Length[occ]]][[2,1]]
]

but I would like to know if there is an easy way to do this using string patterns.

$\endgroup$
5
$\begingroup$

The rules seem to be amenable to a recursive regular expression:

extract[s_] := StringCases[s, RegularExpression["b|c|(a(?R)*d)"]]

extract["abdcbaacdabbdd"]
(* {"abd", "c", "b", "aacdabbdd"} *)

Further examples:

extract["b"]                     (* {"b"} *)
extract["bcbbc"]                 (* {"b", "c", "b", "b", "c"} *)
extract["ad"]                    (* {"ad"} *)
extract["abcd"]                  (* {"abcd"} *)
extract["aadd"]                  (* {"aadd"} *)
extract["aabcddaaabcabdbdd"]     (* {"aabcdd", "aabcabdbdd"} *)
extract["adabdaabcdddaaabbbdd"]  (* {"ad", "abd", "aabcdd", "aabbbdd"} *)
extract["aabdacdd"]              (* {"aabdacdd"} *)

Recursive Patterns: Meaning of (?R)

Mathematica uses the PCRE regular expression engine internally. (?R) is an example of a PCRE recursive pattern -- look for the section labelled "RECURSIVE PATTERNS" in the PCRE documentation. (?R) is a reference to the entire pattern being matched. Be careful to distinguish that this is a reference to the pattern itself, not to the characters matched by the pattern. Thus, the pattern will match "b", "c", or "a...d", where "..." is valid match in its own right according to the whole pattern.

A recursive reference need not refer to the entire pattern. For example, (?1) in the regular expression "b|c|(a((?1)|.)*?d)" refers to the first parenthesized pattern, namely (a((?1)|.)*?d). This permits greater flexibility should it be discovered that the original proposal misses some corner cases.

$\endgroup$
  • $\begingroup$ Wow! This is a very nice construct! Is it possible to translate this RegularExpression into a standard MMA pattern? $\endgroup$ – Aisamu Nov 17 '14 at 17:43
  • 1
    $\begingroup$ @Aisamu There is no direct equivalent in Mathematica's native string pattern syntax. It is probably possible to achieve a similar result using StringCases[s, $patt] where $patt is self-referential. The following pattern comes close, but it fails to preserve proper backtracking: $patt = "b" | "c" | ("a" ~~ (s___ /; StringMatchQ[s, $patt]) ~~ "d"). Even if it worked, it entails an evaluator callback from the PCRE engine for every potential match -- probably more trouble than it is worth. $\endgroup$ – WReach Nov 17 '14 at 18:41
  • $\begingroup$ Very elegant! Could you explain the (?R) please? I will compare timings tomorrow. $\endgroup$ – Marius Ladegård Meyer Nov 17 '14 at 19:02
  • $\begingroup$ I have added the section about recursive patterns. $\endgroup$ – WReach Nov 17 '14 at 20:26
  • $\begingroup$ Thanks, I also found the tutorial "Working with String Patterns" in the docs which helped my understanding a little. As suspected, your code is also the fastest, by a factor of 10 in my test case. Nice! $\endgroup$ – Marius Ladegård Meyer Nov 18 '14 at 7:11
4
$\begingroup$

I was able to match your example, but I'm not sure I completely grasped the problem!

exampleStr = "abdcbaacdabbdd"

checkSubStr[str_String] := 
 And @@ ((Count[Take[Characters@str, #], "a"] >=  Count[Take[Characters@str, #], "d"]) & /@ Range[StringLength@str])

StringCases[exampleStr, 
 Shortest@ tot : ("b" | "c" | (x : ("a" ~~ ___ ~~ "d")) /; 
      And[Count[Characters@x, "a"] == Count[Characters@x, "d"], checkSubStr@x]) :> tot
, Overlaps -> False]

{"abd", "c", "b", "aacdabbdd"}

$\endgroup$
  • 1
    $\begingroup$ Very nice response, I just needed to replace the BlankSequence with a BlankNullSequence to catch the case "ad". Thanks! $\endgroup$ – Marius Ladegård Meyer Nov 17 '14 at 14:31
  • $\begingroup$ Oh, that's right! Corrected! $\endgroup$ – Aisamu Nov 17 '14 at 14:52
2
$\begingroup$

Not anyhere elegant as the OP's own method, but ... staying in the String universe may be a good alternative.

Stealing @Aisamu's string pattern and using only String functions:

ClearAll[cssF, strngCF];
cssF = Function[{s}, And @@ Flatten[{Equal @@ (StringCount[s, #] & /@ {"a", "d"}),
                     (StringCount[#, "a"] >= StringCount[#, "d"] & /@
                            (StringTake[s, #] & /@ Range[-1 + Length@s]))}]];

strngCF = StringCases[#, Shortest@ p: ("b" | "c" | (p2 : ("a" ~~ ___ ~~ "d")) /; cssF[p2]) :> p] &;

Examples:

strngCF@"abdcbaacdabbdd"  (* OP's example *)
(* {"abd","c","b","aacdabbdd"} *)

strngCF@"adadacbcdacdcadbacbd"
(* {"ad","ad","acbcd","acd","c","ad","b","acbd"} *)

strngCF@ "dacacbddaaaacdcdccdd"
(* {"acacbdd","aaaacdcdccdd"} *)
$\endgroup$
  • $\begingroup$ You are missing an "S" on the first instance of "StringCases"! $\endgroup$ – Aisamu Nov 17 '14 at 11:51
  • $\begingroup$ Thanks for the String-centric approach @kguler. I accept your answer, both because it introduced me to StringCount and StringTake, and because it seems to be faster than both my iterative approach, and @Aisamu's answer (tested on 8500 strings of length 15, which is typical for me). $\endgroup$ – Marius Ladegård Meyer Nov 17 '14 at 14:49

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.