Determining the Complexity of Reverse Substrings
Main.java
import java.io.File;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.Random;
import java.util.Scanner;
public class Main {
private static int longestInitialReverseSubstringLength(String y) {
int max = 0;
// sum i from 1 to n: i + (n-i) * i
for (int i = 1; i <= y.length(); i++ ) {
StringBuilder builder = new StringBuilder();
for (int r = i-1; r >= 0; r--) {
builder.append(y.charAt(r));
}
boolean found = false;
String x = builder.toString();
for (int j = 0; j < y.length() - x.length() + 1; j++) {
boolean f = true;
for (int k = 0; k < x.length(); k++) {
if (y.charAt(j + k) != x.charAt(k)) {
f = false;
break;
}
}
if (f) {
found = true;
break;
}
}
if (found) {
max = i;
}
else {
break;
}
}
return max;
}
private static long processLine(String line) {
int length = line.length();
long start = System.currentTimeMillis();
int result = longestInitialReverseSubstringLength(line);
long duration = System.currentTimeMillis() - start;
System.out.println(MessageFormat.format("Length = {0}; Duration = {1}; Result = {2}",
length, duration, result));
return duration;
}
private static int[] generateRandomArray(int N) {
Random random = new Random();
int[] array = new int[N];
for (int i = 0; i
