Pagini recente » Cod sursa (job #1654397) | Cod sursa (job #1925430) | Cod sursa (job #278737) | Cod sursa (job #220896) | Cod sursa (job #1742826)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static int[] preprocess(String pattern) {
int[] F = new int[pattern.length() + 1];
for (int it = 2; it <= pattern.length(); ++it) {
int j = F[it - 1];
while (true) {
if (pattern.charAt(it - 1) == pattern.charAt(j)) {
F[it] = j + 1;
break;
}
if (j == 0) {
F[it] = 0;
break;
}
j = F[j];
}
}
return F;
}
public static int match(String string, String pattern, int[] F, List<Integer> results) {
int answer = 0, stringIndex = 0, patternIndex = 0;
while (true) {
if (stringIndex == string.length()) {
break;
}
if (string.charAt(stringIndex) == pattern.charAt(patternIndex)) {
++stringIndex;
++patternIndex;
if (patternIndex == pattern.length()) {
++answer;
if (results.size() < 1000) {
results.add(stringIndex - pattern.length());
}
patternIndex = F[patternIndex];
}
} else {
if (patternIndex == 0) {
++stringIndex;
} else {
patternIndex = F[patternIndex];
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader("strmatch.in"));
BufferedWriter writer = new BufferedWriter(new FileWriter("strmatch.out"));
String pattern = reader.readLine();
String string = reader.readLine();
int[] F = preprocess(pattern);
List<Integer> results = new ArrayList<>();
int matches = match(string, pattern, F, results);
writer.write(matches + "\n");
for (Integer startPosition : results) {
writer.write(startPosition + " ");
}
reader.close();
writer.close();
}
}