String pattern defined by number of characters

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.

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["abcd"]                  (* {"abcd"} *)
extract["aabcddaaabcabdbdd"]     (* {"aabcdd", "aabcabdbdd"} *)
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.

• Wow! This is a very nice construct! Is it possible to translate this RegularExpression into a standard MMA pattern? Nov 17, 2014 at 17:43
• @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. Nov 17, 2014 at 18:41
• Very elegant! Could you explain the (?R) please? I will compare timings tomorrow. Nov 17, 2014 at 19:02
• I have added the section about recursive patterns. Nov 17, 2014 at 20:26
• 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! Nov 18, 2014 at 7:11

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"}

• Very nice response, I just needed to replace the BlankSequence with a BlankNullSequence to catch the case "ad". Thanks! Nov 17, 2014 at 14:31
• Oh, that's right! Corrected! Nov 17, 2014 at 14:52

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"} *)


• 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). Nov 17, 2014 at 14:49