Computing desk
< April 18	<< Mar \| April \| May >>	April 20 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 19

detecting non-overlapping repetitions

I'm trying to way to detect all the non-overlapping repetitions within a given string. I Googled it and Stackoverflow gave me an excellent solution that's exactly what I wanted[1], except it doesn't work. To clarify, it appears bug-free and works as advertised for most string, but it's misbehaving for some reason for the type of strings I'm working with:

   %2FCatSearch%2F155%2Fengraving-tools%2F32&=%2FCatSearch%2F155%2Fengraving-tools%2F36%2C%2FCatSearch%2F155%2Fengraving-tools%2F32%2C%2FCatSearch%2F155%2Fengraving-tools%2F30%2C%2FCatSearch%2F155%2Fengraving-tools%2F26%2C%2FCatSearch%2F155%2Fengraving-tools%2F21%2C%2FCatSearch%2F155%2Fengraving-tools%2F16%2C%2FCatSearch%2F155%2Fengraving-tools%2F11&v=j&facet=%5B%5B%22vend_name%22%2C%22vend_name%22%2C%22Harvey%22%5D%5D

1. Why is my string not working for the repetitions function?

2. Or alternatively, is there another working solution to the problem? ECS LIVA Z (talk) 20:58, 19 April 2017 (UTC)[reply]

The solution you linked to finds CONSECUTIVE repetitions; that is, repetitions with no extra characters appearing between the repeated strings. Your example does not have any such repetitions (except the string "55" where "5" is repeated). What type of repetition are you trying to find? Do you want to find cases where the substring is repeated anywhere in the string, with arbitrary strings appearing between the repeated substrings? CodeTalker (talk) 22:05, 19 April 2017 (UTC)[reply]

Ah, that's it. Thanks. I'm not sure how to modify the regex though.

Yes, in my case arbitrary strings can appear between the repeated substrings. ECS LIVA Z (talk) 22:17, 19 April 2017 (UTC)[reply]

Also in my case all the repeated substrings appear to be longer than 6 characters, so this should help on the runtime complexity part. (counting arbitrary length repeated substrings is probably O(n^3) or even harder). ECS LIVA Z (talk) 22:20, 19 April 2017 (UTC)[reply]

In Perl the regexp (.{6,})(.*\1){3} will match a string that contains at least 4 (i.e. 3+1) non-overlapping instances of the same substring of length at least 6, and sets $1 to the repeated substring. But I don't know a way to generalize it so that it tells you how many times the substring is repeated. --76.71.6.254 (talk) 22:59, 19 April 2017 (UTC)[reply]

Yeah, I tried this but it doesn't work:

   def repetitions(s):
      r = re.compile(r"(.{6,}?)\1+")
      for match in r.finditer(s):
          yield (match.group(1), len(match.group(0))/len(match.group(1)))

The regex part is pretty tricky. I'm not sure how to get past the consecutive repetitions part. ECS LIVA Z (talk) 23:14, 19 April 2017 (UTC)[reply]

My pseudocode below uses array indices that start at 1.

If I understand the problem correctly, you want to take as input a string, and return a list of all substrings that are present more that once in S and their repetition indices. So for instance shazhama should return ['h',(2,4);'a',(3,5,7);'ha',(2,4)].

Depending on your computation time constraints, the brutal solution can be enough (O(n^3) does not look too bad):

Define N = length(S)
Initialize result_list as empty
For i from 1 to N
  For j from i to N
    Define snippet=S[i:j]
      If (snippet is not already in result_list)
        Define list_k = every index such that S[k:k+j-i]==snippet;
        If list_k contains more than one element
          Add [snippet, list_k] to result_list
        End If
      End If
  End For
End For
Return result_list

Regexping can give elegant solutions, but efficient solutions are good, too. Tigraan^{Click here to contact me} 16:26, 21 April 2017 (UTC)[reply]

Thank you so much! This is excellent. ECS LIVA Z (talk) 18:47, 21 April 2017 (UTC)[reply]

Extending a network attaching an eth

I want to extend the range of my wi-fi to cover two flats in different floors. For that, I'd want to connect an eth cable to a router's eth port, pass the cable through the stairs (20m), and attach some device at the other end, so that the recipient also gets a wireless connection. I don't want to use a repeater to make the wireless signal more powerful nor those networks through routers connected to the power lines.

What device would I have to connect to the other end of the cable? Would this device also need to be plugged? --Hofhof (talk) 21:03, 19 April 2017 (UTC)[reply]

What you want is a wireless access point. It will need to have a connection to your router to be a part of your network, so you'll still need to plumb that cat6.

ᛗᛁᛟᛚᚾᛁᚱPants Tell me all about it.

21:30, 19 April 2017 (UTC)[reply]

So, I connect a cat6 to my router and the WAP at the other end? And does the WAP get its power from the cat6, like a mouse, keyboard or external HDD get the power from the USB cable?--Hofhof (talk) 22:21, 19 April 2017 (UTC)[reply]

Sorry for the late response. No, the WAP will need power from its own adapter. Each WAP should come with a power adapter and cable when you order it. Ethernet can't carry power the way USB can.

ᛗᛁᛟᛚᚾᛁᚱPants Tell me all about it.

17:38, 21 April 2017 (UTC)[reply]

Google Power over Ethernet and ensure that whatever WAP you pickup can be powered in this manner. This is very common, requires no configuration, and is easy to use. 97.102.87.227 (talk) 23:40, 22 April 2017 (UTC) — Preceding unsigned comment added by 97.102.87.227 (talk) 23:39, 22 April 2017 (UTC)[reply]