git.iko.soy/bat
on bce304a help sign in
bat/tests/syntax-tests/source/Ruby/output.rb
56 lines 1.4 kB history raw
1class RepeatedSubstring
2 def find_repeated_substring(s)
3 # catch the edge cases
4 return 'NONE' if s == ''
5 # check if the string consists of only one character => "aaaaaa" => "a"
6 return s.split('').uniq[0] if s.split('').uniq.length == 1
8 searched = []
9 longest_prefix = 0
10 long_prefix = ''
11 (0..s.length - 1).each do |i|
12 next if searched.include? s[i]
14 searched.push(s[i])
15 next_occurrences = next_index(s, i + 1, s[i])
16 next_occurrences.each do |next_occurrence|
17 next if next_occurrence == -1
19 prefix = ge_prefix(s[i..next_occurrence - 1], s[next_occurrence..s.length])
20 if prefix.length > longest_prefix
21 longest_prefix = prefix.length
22 long_prefix = prefix
23 end
24 end
25 end
26 # if prefix == " " it is a invalid sequence
27 return 'NONE' if long_prefix.strip.empty?
29 long_prefix
30 end
32 def get_prefix(s1, s2)
33 prefix = ''
34 min_length = [s1.length, s2.length].min
35 return '' if s1.nil? || s2.nil?
37 (0..min_length - 1).each do |i|
38 return prefix if s1[i] != s2[i]
40 prefix += s1[i]
41 end
42 prefix
43 end
45 def next_index(seq, index, value)
46 indexes = []
47 (index..seq.length).each do |i|
48 indexes.push(i) if seq[i] == value
49 end
50 indexes
51 end
53 def find_repeated_substring_file(file_path)
54 File.open(file_path).read.each_line.map { |line| find_repeated_substring(line) }
55 end
56end