1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.concurrent.ThreadLocalRandom;
public class HashSubstring {
private static FastScanner in;
private static PrintWriter out;
public static void main(String[] args) throws IOException {
in = new FastScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
printOccurrences(rabinKarp(readInput()));
out.close();
}
private static Data readInput() throws IOException {
String pattern = in.next();
String text = in.next();
return new Data(pattern, text);
}
private static void printOccurrences(List<Integer> ans) {
for (Integer cur : ans) {
out.print(cur);
out.print(" ");
}
}
static List<Integer> getOccurrences(Data input) {
String s = input.pattern, t = input.text;
int m = s.length(), n = t.length();
List<Integer> occurrences = new ArrayList<>();
for (int i = 0; i + m <= n; ++i) {
boolean equal = true;
for (int j = 0; j < m; ++j) {
if (s.charAt(j) != t.charAt(i + j)) {
equal = false;
break;
}
}
if (equal)
occurrences.add(i);
}
return occurrences;
}
static class Data {
String pattern;
String text;
Data(String pattern, String text) {
this.pattern = pattern;
this.text = text;
}
}
static long polyHash(String S, int p, int x) {
long hash = 0;
for (int i = S.length() - 1; i >= 0; --i)
hash = (hash * x + S.charAt(i)) % p;
return hash;
}
static long[] preComputeHashes(String T, int pattenLength, int p, int x) {
long[] H = new long[T.length() - pattenLength + 1];
String S = T.substring(T.length() - pattenLength);
H[T.length() - pattenLength] = polyHash(S, p, x);
long y = 1;
for (int i = 0; i < pattenLength; i++) {
y = (y * x) % p;
}
for (int i = T.length() - pattenLength - 1; i >= 0; --i) {
H[i] = (x * H[i + 1] + T.charAt(i) - y * T.charAt(i + pattenLength)) % p;
}
return H;
}
static List<Integer> rabinKarp(Data input) {
String T = input.text;
String P = input.pattern;
int p = 1000000007;
int x = ThreadLocalRandom.current().nextInt(1, p);
List<Integer> positions = new ArrayList<>();
long pHash = polyHash(P, p, x);
long[] H = preComputeHashes(T, P.length(), p, x);
for (int i = 0; i < T.length() - P.length() + 1; i++) {
if (pHash != H[i]) {
continue;
}
if (T.substring(i, i + P.length()).equals(P))
positions.add(i);
}
return positions;
}
static List<Integer> rabinKarp(String P, String T) {
int p = 1000000007;
int x = ThreadLocalRandom.current().nextInt(1, p);
List<Integer> positions = new ArrayList<>();
long pHash = polyHash(P, p, x);
long[] H = preComputeHashes(T, P.length(), p, x);
for (int i = 0; i < T.length() - P.length() + 1; i++) {
if (pHash != H[i]) {
continue;
}
if (T.substring(i, i + P.length()).equals(P))
positions.add(i);
}
return positions;
}
static class FastScanner {
private BufferedReader reader;
private StringTokenizer tokenizer;
FastScanner() {
reader = new BufferedReader(new InputStreamReader(System.in));
tokenizer = null;
}
String next() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
}
}
|
