# How to extract strings from the list with an additional condition on previous elements?

There are a long list of strings $s$ and two lists of substrings $s1$ and $s2$. I want to take all elements of $s$ which contain a substring from $s2$ and such that before it on no more than $n$ places there is a string containing a substring from $s1$. For example, if

s={"a","b1","c","b2","a","c","b3"};
s1={"a"} ;
s2={"b"};
n=2;


the result should be {"b1","b3"} because two previous to "b2" elements don't contain substring "a".

It can be done with the help of Position, creating and comparing two lists of elements positions with fragments from $s1$ and $s2$. Is there a more direct way without creating additional lists?

• I note that each of the three methods posted produce different results. I don't know which if any is correct. Jul 22, 2012 at 11:21
• I want to take another crack at this. Please clarify: is a string containing both "a" and "b" to automatically be returned? Jul 22, 2012 at 14:03
• Yes, all strings containing "b" to be returned. Jul 22, 2012 at 14:49
• Andrew, certainly you don't mean any string anywhere containing "b" is to be returned, so I'm still not clear on that. Please see my second answer and tell me which (if either) behavior is as you want. Jul 22, 2012 at 14:52
• You mean "such that in it's n previous positions there is at least one string containing a substring of s1"?
– Rojo
Jul 22, 2012 at 22:29

Second attempt, working on the assumption that "axb" should not be returned:

s = {"a", "b1", "c", "b2", "a", "c", "b3", "axb"};
s1 = {"a"};
s2 = {"b"};
n = 2;

f = (If[# > 0 && ! StringFreeQ[#2, s2], Sow@#2];
If[! StringFreeQ[#2, s1], n, # - 1]) &;

Reap[Fold[f, 0, s]][[2, 1]]

{"b1", "b3"}


If "axb" should be returned, then:

f = (If[! StringFreeQ[#, s1], i = n, --i];
If[i >= 0 && ! StringFreeQ[#, s2], Sow@#]) &;

Reap[i = 0; Scan[f, s]][[2, 1]]

{"b1", "b3", "axb"}


Since this answer was Accepted I guess I'm on the right path. I shall provide an additional method designed for speed using ListCorrelate (inspired by R.M's answer) and Pick.

bin = 1 - Boole@StringFreeQ[s, #] &;

Pick[
s,
bin[s2] ListCorrelate[ConstantArray[1, n + 1], bin[s1], n + 1, 0] // Unitize,
1
]

{"b1", "b3", "axb"}


If you want the behavior that does not return "axb" use ConstantArray[1, n].

• @R.M I think I should combine the answers and include performance testing as they exchange places depending on the data. Now is not the time however. Poke me if I don't get back to it in 24 hours. Jul 22, 2012 at 16:14

ReplaceList[s,{___,p:Repeated[_,n]/;!StringFreeQ[StringJoin@p,s1],x_/;!StringFreeQ[x,s2],___}:>x]

• Thanks. It could give repeated strings in the answer. Jul 22, 2012 at 13:40

Here's a solution using ListCorrelate:

test[list_, pat1_, pat2_] /; ! StringFreeQ[Last@list, pat1] :=
Last@list /; ! StringFreeQ[StringJoin@Most@list, pat2]
test[_, _, _] := ## &[]

ListCorrelate[ConstantArray[1, n + 1], s, {-1, -1}, {""}, ##2 &, test[{##}, s2, s1] &]
(* {"b1", "b3"} *)


I'm not sure if this counts as "creating additional lists", but it seems to work:

With[{s = {"a", "b1", "c", "b2", "a", "c", "b3"}, s1 = {"a"}, s2 = {"b"}, n = 2},
Last /@ Select[Partition[s, n + 1, 1, {-1, -1}, {}],
! (StringFreeQ[Last[#], s2] || And @@ StringFreeQ[Most[#], s1]) &]]

• thanks for the idea. It doesn't work for $n\ne2$, but probably it can be mended just changing Partition options. Jul 22, 2012 at 13:16
• Could you give an example of a case where this construction doesn't work? I have a possible tweak in mind, but I'd like to be sure if it'll work in those cases you mention... Jul 22, 2012 at 14:06
• It gives "b3" for $n=3$ in this example and for $n=1$ produces an error message. Jul 22, 2012 at 14:52
• Try the current version now. Jul 22, 2012 at 14:54

This is probably similar to what you alluded to in the question but perhaps it is helpful anyway:

s = {"a", "b1", "c", "b2", "a", "c", "b3", "axb"};
s1 = {"a"};
s2 = {"b"};
n = 2;

Cases[
s[[Max[1, # - n] ;; #]] & @@@ Position[StringFreeQ[s, s2], False],
{x__, b_} /; ! StringFreeQ["" <> x, s1] :> b
]

{"b1", "b3"}


If it is desired to return "axb" in the example above use StringFreeQ[x <> b, s1]

• thanks, it work correctly if for "b" on a segment [#,#+n] there is only one element with "a". Otherwise there will be multiple copies of the same string in the result. Jul 22, 2012 at 13:23
• @Andrew You're right of course. I'm sorry but I don't have time to fix this now. Jul 22, 2012 at 13:53
• @Andrew I have revised this answer to address the problem. Please let me know if it works. I still do not know if you want to return e.g. "axb" automatically. Jul 22, 2012 at 14:37