1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.*;
public class FindSubstringTests {
public String makeWord() {
String testWord = "";
String charSet = "abcdefghijklMNOPQRSTUVWXYZ1234567890)(*&^% `<>?/}{+=";
Random r = new Random();
for (int i = 0; i < r.nextInt(145)+60; i++){
testWord = testWord += charSet.charAt(r.nextInt(charSet.length()));
}
return testWord;
}
public int lSubstring(String a, String b) {
char[] aPlusB = a.concat(b).toCharArray();
char[] bPlusA = b.concat(a).toCharArray();
// Determine the characters shared by both strings
char[] aChars = a.toCharArray();
char[] bChars = b.toCharArray();
LinkedHashSet<Character> aCharsSet = new LinkedHashSet<Character>();
LinkedHashSet<Character> bCharsSet = new LinkedHashSet<Character>();
for (char character : aChars) {
aCharsSet.add(character);
}
for (char character : bChars) {
bCharsSet.add(character);
}
aCharsSet.retainAll(bCharsSet);
//aCharsSet now holds the characters shared by the strings
int temp = 0;
int maxLength = 0;
// Check each character of aPlusB to see if it's in the set of shared characters
for (int i = 0; i < aPlusB.length; i++) {
if (!aCharsSet.contains(aPlusB[i])) {
// If it isn't, increment temp. temp represents the longest current length of unshared characters.
temp++;
if (temp > maxLength) {
// If temp is greater than the stored max value, update the max value
maxLength = temp;
}
} else {
// Otherwise, reset the length to zero
temp = 0;
}
}
// Repeat the process for B + A
temp = 0;
for (int i = 0; i < bPlusA.length; i++) {
if (!aCharsSet.contains(bPlusA[i])) {
temp++;
if (temp > maxLength) {
maxLength = temp;
}
} else {
temp = 0;
}
}
return maxLength;
}
@Test
public void test() {
assertEquals("Basic test ('preface', 'singularity')", 8, FindSubstring.longestSubstring("preface","singularity"));
assertEquals("Long strings", 607, FindSubstring.longestSubstring(";;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5;;;;;;;;;;;;ZZZZ5535533553355355335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533555335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533555335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533555335533553355355335533553355355335533553355533553355335535533553355335535533553355335553355335533553553355335533553553355335533535535533553355335535533553355335535533553355335533553355335535533553355335533113355335533553355335511","01000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100101010010101001010101010010001000100Z10101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001000100010010101001010100101010101001001"));
assertEquals("Anagrams ('tablets', 'battles')", 0, FindSubstring.longestSubstring("tablets","battles"));
assertEquals("Whitespace and escape characters", 5, FindSubstring.longestSubstring(" \t","\n445 "));
assertEquals("Substring entirely in B", 6, FindSubstring.longestSubstring("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb","beliefs"));
assertEquals("Substring entirely in A", 6, FindSubstring.longestSubstring("hotdogs","sssssssssssssssssss"));
assertEquals("Substring mid A", 3, FindSubstring.longestSubstring("e1222111100011112221f","12eeeeeeeffffffff"));
assertEquals("Substring mid B", 4, FindSubstring.longestSubstring("&&&&&&&&&&&&&&$$$$$$$$$$$$GGGG","$$$$$$$$$G$$$$$hamo&&&&&&&&&&&&&&&&&&&"));
assertEquals("No shared characters ('rhythms', 'logician')", 15, FindSubstring.longestSubstring("rhythms","logician"));
assertEquals("Lots of shared characters", 6, FindSubstring.longestSubstring("abcd`efgh';lij1|234@5\678[90klmnopqrstsrqponmlk","tsrq6\789p[`onmlkvutlsrqp12;345onm|lk'jihgfedcba0uvwxyz@"));
assertEquals("Two empty strings", 0, FindSubstring.longestSubstring("",""));
assertEquals("One empty string", 8, FindSubstring.longestSubstring("","06032016"));
// THE RANDOM TESTS!!!!!!!!
String[] randomTestsA = {makeWord(), makeWord(),makeWord(),makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord()};
String[] randomTestsB = {makeWord(), makeWord(),makeWord(),makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord(),
makeWord(), makeWord(), makeWord(), makeWord(), makeWord(), makeWord()};
for (int i = 0; i < randomTestsA.length; i++) {
assertEquals("Random test " + i + 1 + "/58" + " (" + randomTestsA[i] + ", " + randomTestsB[i] + ") " , lSubstring(randomTestsA[i],randomTestsB[i]), FindSubstring.longestSubstring(randomTestsA[i],randomTestsB[i]));
}
}
}
|