Pagini recente » Cod sursa (job #1113165) | Cod sursa (job #259985) | Cod sursa (job #1060215) | Cod sursa (job #985080) | Cod sursa (job #2083360)
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 int prime = 49157;
private static int childHash;
private static int childLength;
private static int parentLength;
private static List<Integer> output = new ArrayList<>();
private static int hash(String input) {
int h = 0;
for (int i = 0; i < input.length(); i++) {
h += ((int) input.charAt(i)) * Math.pow(prime, i);
}
return h;
}
private static int nextHash(char oldChar, char nextChar, int oldHash, int length) {
return (int) ((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;
}
int 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());
for (Integer integer : output) {
printWriter.printf("%d ", integer);
}
}
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();
}
}
}