RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a lot of string searching. (Note that this ends today.)

Task 1: Reverse Existence

You are given a string.

Write a script to find whether any substring of length 2 is also present in the reverse of the given string.

Everything I was writing in has some sort of string-in-string search, and can be bodged to have a sliding window.

sub reverseexistence($a) {

Initialise return value.

  my $ret = 0;

Set up reversed main string as an array of characters. (Doing it as a string would also have worked.)

  my @c = reverse split('', $a);

In a 2-element sliding window on that array of characters,

  slide {

Set up a "sample" string of those two characters,

    my $sample = $::a . $::b;

and if it's found in the original string,

    if (index($a, $sample) > -1) {

set the return value true. (Really I should early return at this point, as I did in some of the other code. I'd probably just been writing Scala, where you can't abort a loop.)

      $ret = 1;
    }
  } @c;
  $ret;
}

Task 2: Prefix Suffix

You are given an array of strings.

Write a script to find if the two strings (str1, str2) in the given array such that str1 is prefix and suffix of str2. Return the total count of such pairs.

(There's some question as to whether two matching strings should count as prefix-suffix of each other, or not at all, or only in one direction. I ended up writing the latter.)

This gets a little more fiddly, but most of the languages I'm using have a "find the last occurrence" string search, For example Python:

def prefixsuffix(a0):

Set total to zero.

  tot = 0

Sort the input list by length.

  a = a0
  a.sort(key = len)

Test each shorter string against each potentially longer string. (If they're identical, the order doesn't matter.)

  for si in range(len(a) - 1):
    for li in range(si + 1, len(a)):

If the shorter string occurs at the start of the longer, and at the end (which I have to work out based on both string lengths), increment the total.

      if a[li].find(a[si]) != -1 and a[li].rfind(a[si]) == len(a[li]) - len(a[si]):
        tot += 1
  return tot

A language that doesn't have that kind of search is PostScript. Mostly it starts as before.

/prefixsuffix {
    0 dict begin
    { length } quicksort.with_keygen /a exch def
    0
    0 1 a length 2 sub {
        /si exch def
        si 1 add 1 a length 1 sub {
            /li exch def

anchorsearch is a shorthand method for a search that only matches at the start of the string. We discard the search results.

            a li get a si get anchorsearch {
                pop pop

Now we reverse both the sample strings, and do another anchorsearch.

                a li get s2a reverse a2s
                a si get s2a reverse a2s
                anchorsearch {
                    pop pop
                    1 add
                } {
                    pop
                } ifelse
            } {
                pop
            } ifelse
        } for
    } for
    end
} bind def

If I'd got round to doing it in Lua as well, I'd probably have done a global match, and looked at the first and last results.

Full code on codeberg.