Pagini recente » Cod sursa (job #405453) | Cod sursa (job #2221735) | Cod sursa (job #2386654) | Cod sursa (job #785785) | Cod sursa (job #1743625)
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 {
private static long SYMBOLS = 52;
private static long MODULO1 = 1999999973;
private static long MODULO2 = 1999999943;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader("strmatch.in"));
BufferedWriter writer = new BufferedWriter(new FileWriter("strmatch.out"));
char[] pattern = reader.readLine().toCharArray();
char[] string = reader.readLine().toCharArray();
if (pattern.length > string.length) {
writer.write("0");
} else {
long matches = 0, patternHash1 = 0, patternHash2 = 0, stringHash1 = 0, stringHash2 = 0, symbolsPower1 = 1,
symbolsPower2 = 1;
List<Integer> matchesStart = new ArrayList<>();
for (int it = pattern.length - 1; it >= 0; --it) {
patternHash1 = (patternHash1 + symbolsPower1 * pattern[it] % MODULO1) % MODULO1;
patternHash2 = (patternHash2 + symbolsPower2 * pattern[it] % MODULO2) % MODULO2;
stringHash1 = (stringHash1 + symbolsPower1 * string[it] % MODULO1) % MODULO1;
stringHash2 = (stringHash2 + symbolsPower2 * string[it] % MODULO2) % MODULO2;
if (it != 0) {
symbolsPower1 = (symbolsPower1 * SYMBOLS) % MODULO1;
symbolsPower2 = (symbolsPower2 * SYMBOLS) % MODULO2;
}
}
if (patternHash1 == stringHash1 && patternHash2 == stringHash2) {
++matches;
matchesStart.add(0);
}
for (int it = pattern.length; it < string.length; ++it) {
int prevStartIndex = it - pattern.length;
stringHash1 = (SYMBOLS * (stringHash1 - (symbolsPower1 * string[prevStartIndex] % MODULO1) + MODULO1) + string[it]) % MODULO1;
stringHash2 = (SYMBOLS * (stringHash2 - (symbolsPower2 * string[prevStartIndex] % MODULO2) + MODULO2) + string[it]) % MODULO2;
if (patternHash1 == stringHash1 && patternHash2 == stringHash2) {
++matches;
if (matchesStart.size() < 1000)
matchesStart.add(prevStartIndex + 1);
}
}
writer.write(matches + "\n");
for (Integer it : matchesStart) {
writer.write(it + " ");
}
}
reader.close();
writer.close();
}
}