StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What you have here can conceptually be solved with a sliding window. For your example, you have a sliding window of size 3.</p> <p>For each character in the string, you take the substring of the current character and the next two characters as the current pattern. You then slide the window up one position, and check if the remainder of the string has what the current pattern contains. If it does, you return the current index. If not, you repeat.</p> <p>Example:</p> <pre><code>1010101101 |-| </code></pre> <p>So, pattern = <code>101</code>. Now, we advance the sliding window by one character:</p> <pre><code>1010101101 |-| </code></pre> <p>And see if the rest of the string has <code>101</code>, checking every combination of 3 characters.</p> <p>Conceptually, this should be all you need to solve this problem. </p> <p><strong>Edit:</strong> I really don't like when people just ask for code, but since this seemed to be an interesting problem, here is my implementation of the above algorithm, which allows for the window size to vary (instead of being fixed at 3, the function is only briefly tested and omits obvious error checking):</p> <pre><code>function findPattern( $str, $window_size = 3) { // Start the index at 0 (beginning of the string) $i = 0; // while( (the current pattern in the window) is not empty / false) while( ($current_pattern = substr( $str, $i, $window_size)) != false) { $possible_matches = array(); // Get the combination of all possible matches from the remainder of the string for( $j = 0; $j < $window_size; $j++) { $possible_matches = array_merge( $possible_matches, str_split( substr( $str, $i + 1 + $j), $window_size)); } // If the current pattern is in the possible matches, we found a duplicate, return the index of the first occurrence if( in_array( $current_pattern, $possible_matches)) { return $i; } // Otherwise, increment $i and grab a new window $i++; } // No duplicates were found, return -1 return -1; } </code></pre> <p>It should be noted that this certainly isn't the most efficient algorithm or implementation, but it should help clarify the problem and give a straightforward example on how to solve it.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload