# 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. –  Mr.Wizard Jul 22 '12 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? –  Mr.Wizard Jul 22 '12 at 14:03
Yes, all strings containing "b" to be returned. –  Andrew Jul 22 '12 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. –  Mr.Wizard Jul 22 '12 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 '12 at 22:29
show 1 more comment

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. –  Mr.Wizard Jul 22 '12 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. –  Andrew Jul 22 '12 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. –  Andrew Jul 22 '12 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 '12 at 14:06
It gives "b3" for $n=3$ in this example and for $n=1$ produces an error message. –  Andrew Jul 22 '12 at 14:52
Try the current version now. –  Ｊ. Ｍ. Jul 22 '12 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. –  Andrew Jul 22 '12 at 13:23
@Andrew You're right of course. I'm sorry but I don't have time to fix this now. –  Mr.Wizard Jul 22 '12 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. –  Mr.Wizard Jul 22 '12 at 14:37