Pagini recente » Cod sursa (job #93214) | Cod sursa (job #483085) | Cod sursa (job #349726) | Cod sursa (job #1111542) | Cod sursa (job #1743591)
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 MODULO = 1999999973;
private static long pow(long x, long power) {
long answer = 1;
while (power-- > 0) {
answer *= x;
answer %= MODULO;
}
return answer;
}
private static long[] hashString(String string, int sequenceLength) {
long[] hashes = new long[string.length() - sequenceLength + 1];
for (int it = 0; it < sequenceLength; ++it) {
hashes[0] = ((SYMBOLS * hashes[0]) % MODULO + string.charAt(it)) % MODULO;
}
long power = pow(SYMBOLS, sequenceLength - 1);
for (int it = sequenceLength; it < string.length(); ++it) {
int index = it - sequenceLength;
hashes[index + 1] = (SYMBOLS * (hashes[index] - ((power * string.charAt(index)) % MODULO) + MODULO )) % MODULO;
hashes[index + 1] = (hashes[index + 1] + string.charAt(it)) % MODULO;
}
return hashes;
}
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();
if (pattern.length() > string.length()) {
writer.write("0");
} else {
long[] hashes = hashString(string, pattern.length());
long[] patternHash = hashString(pattern, pattern.length());
long matches = 0;
List<Integer> matchesStart = new ArrayList<>();
for (int it = 0; it < hashes.length; ++it) {
if (hashes[it] == patternHash[0]) {
boolean isOk = true;
for (int jt = 0; jt < pattern.length() && isOk; ++jt) {
if (string.charAt(it + jt) != pattern.charAt(jt))
isOk = false;
}
if (isOk) {
++matches;
if (matchesStart.size() < 1000) {
matchesStart.add(it);
}
}
}
}
writer.write(matches + "\n");
for (Integer it : matchesStart) {
writer.write(it + " ");
}
}
reader.close();
writer.close();
}
}