Pagini recente » Cod sursa (job #1780306) | Istoria paginii utilizator/georgiana321 | Cod sursa (job #616705) | Istoria paginii runda/11dlabparcurgeri | Cod sursa (job #2083367)
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static PrintWriter printWriter;
private static MyScanner scanner;
private static final long prime = 12289;
private static long childHash;
private static int childLength;
private static int parentLength;
private static List<Integer> output = new ArrayList<>();
private static long hash(String input) {
long h = 0;
for (int i = 0; i < input.length(); i++) {
h += ((int) input.charAt(i)) * Math.pow(prime, i);
}
return h;
}
private static long nextHash(char oldChar, char nextChar, long oldHash, int length) {
return (long) ((oldHash - (int) oldChar)/prime + ((int) nextChar) * Math.pow(prime, length - 1));
}
public static void main(String[] args) throws IOException {
scanner = new MyScanner("strmatch.in");
printWriter = new PrintWriter("strmatch.out");
String child = scanner.next();
String parent = scanner.next();
childHash = hash(child);
childLength = child.length();
parentLength = parent.length();
if (parentLength < childLength) {
printWriter.printf("0");
return;
}
long h = hash(parent.substring(0, childLength));
if (h == childHash)
output.add(0);
for (int i = childLength; i < parentLength; i++) {
h = nextHash(parent.charAt(i - childLength), parent.charAt(i), h, childLength);
if (h == childHash)
output.add(i - childLength + 1);
}
printWriter.printf("%d\n", output.size());
int size = output.size();
if (size > 1000)
size = 1000;
for (int i = 0; i < size; i++)
printWriter.printf("%d ", output.get(i));
printWriter.close();
scanner.close();
}
private static class MyScanner
{
private BufferedReader bufferedReader;
private StringTokenizer stringTokenizer;
MyScanner(String filename) throws FileNotFoundException {
bufferedReader = new BufferedReader(new FileReader(filename));
}
private String next() throws IOException {
while(stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
}
return stringTokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt( next() );
}
void close() throws IOException {
bufferedReader.close();
}
}
}