Pagini recente » Cod sursa (job #2855476) | Cod sursa (job #498092) | Cod sursa (job #980038) | Cod sursa (job #1433209) | Cod sursa (job #2229397)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
InputStream inputStream = new FileInputStream("strmatch.in");
OutputStream outputStream = new FileOutputStream("strmatch.out");
try (InputReader inputReader = new InputReader(inputStream);
PrintWriter printWriter = new PrintWriter(outputStream)) {
String smallString = inputReader.nextToken();
String largeString = inputReader.nextToken();
Solver.solve(smallString.toCharArray(), largeString.toCharArray(), printWriter);
}
}
static class Solver {
private static int[] largestPrefixSuffix(char[] str) {
int[] result = new int[str.length];
Arrays.fill(result, -1);
int longestPrefixSuffix = -1;
for (int idx = 1; idx < str.length; idx++) {
while (longestPrefixSuffix != -1 && str[longestPrefixSuffix + 1] != str[idx]) {
longestPrefixSuffix = result[longestPrefixSuffix];
}
if (str[longestPrefixSuffix + 1] == str[idx]) {
longestPrefixSuffix++;
}
result[idx] = longestPrefixSuffix;
}
return result;
}
public static void solve(char[] smallString, char[] largeString, PrintWriter printWriter) {
int[] longestPrefixSuffix = largestPrefixSuffix(smallString);
int longestSuffixMatch = -1, countMatches = 0;
int[] topThousandMatches = new int[1000];
for (int idx = 0; idx < largeString.length; idx++) {
while (longestSuffixMatch != -1 && smallString[longestSuffixMatch + 1] != largeString[idx]) {
longestSuffixMatch = longestPrefixSuffix[longestSuffixMatch];
}
if (smallString[longestSuffixMatch + 1] == largeString[idx]) {
longestSuffixMatch++;
}
if (longestSuffixMatch == smallString.length - 1) {
if (countMatches < 1000) {
topThousandMatches[countMatches] = idx - smallString.length + 1;
}
countMatches++;
longestSuffixMatch = longestPrefixSuffix[longestSuffixMatch];
}
}
printWriter.println(countMatches);
for (int matchNo = 0, totalMatches = Math.min(1000, countMatches); matchNo < totalMatches; matchNo++) {
printWriter.print(topThousandMatches[matchNo] + " ");
}
printWriter.println();
}
}
static class InputReader implements AutoCloseable {
private BufferedReader bufferedReader;
private StringTokenizer stringTokenizer;
public InputReader(InputStream inputStream) {
bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
stringTokenizer = null;
}
private String nextToken() {
if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
try {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return stringTokenizer.nextToken();
}
@Override
public void close() throws IOException {
bufferedReader.close();
}
}
}