Rosalind - Locating Restriction Sites

Sep 1, 2019 rosalind

Problem:

Please find the problem here.

Solution:

A restriction site is basically a palindrome (with the complement twist). I modified the Manacher’s algorithm to solve this problem.

First, when trying to expand to find palindrome half-length, I apply the complement rule.

Second, I skipped the ‘#’ sign thing because we knew all palindromes will be of even length.

Code: