-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash_str_one_modulo.java
156 lines (122 loc) · 4.08 KB
/
hash_str_one_modulo.java
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
package competitive;
import java.io.*;
import java.util.Locale;
import java.util.StringTokenizer;
public class Competitive implements Runnable {
private final static int MAX_STACK_SIZE = 128;
private final static int STRING_MAX_SIZE = 100001;
//////////////////////////////////////////////////////////////////
long sqrtLong(long x) {
long root = (long)Math.sqrt(x);
while (root * root > x) --root;
while ((root + 1) * (root + 1) <= x) ++root;
return root;
}
//////////////////////////////////////////////////////////////////
private boolean yesNo(boolean yes) {
return yesNo(yes, "YES", "NO");
}
private boolean yesNo(boolean yes, String yesString, String noString) {
out.println(yes ? yesString : noString);
return yes;
}
//////////////////////////////////////////////////////////////////
private long readLong() {
return Long.parseLong(readString());
}
private int[] readIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; ++i) a[i] = readInt();
return a;
}
private int readInt() {
return Integer.parseInt(readString());
}
private String readString() {
while (!tok.hasMoreTokens()) {
String nextLine = readLine();
if (null == nextLine) return null;
tok = new StringTokenizer(nextLine);
}
return tok.nextToken();
}
private String readLine() {
try {
return in.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
//////////////////////////////////////////////////////////////////
private BufferedReader in;
private StringTokenizer tok;
private PrintWriter out;
private void initFileIO(String inputFileName, String outputFileName) throws FileNotFoundException {
in = new BufferedReader(new FileReader(inputFileName));
out = new PrintWriter(outputFileName);
}
private void initConsoleIO() throws IOException {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
}
private void initIO() throws IOException {
Locale.setDefault(Locale.US);
String fileName = "";
if (!fileName.isEmpty()) {
initFileIO(fileName + ".in", fileName + ".out");
} else {
if (new File("input.txt").exists()) {
initFileIO("input.txt", "output.txt");
} else {
initConsoleIO();
}
}
tok = new StringTokenizer("");
}
//////////////////////////////////////////////////////////////////
public void run() {
try {
long timeStart = System.currentTimeMillis();
initIO();
solve();
out.close();
// long timeEnd = System.currentTimeMillis();
// System.err.println("Time(ms) = " + (timeEnd - timeStart));
} catch (Exception e) {
e.printStackTrace();
throw new RuntimeException(e);
}
}
public static void main(String[] args) {
new Thread(null, new Competitive(), "", MAX_STACK_SIZE * (1L << 20)).start();
}
////
private void solve() {
Hash.initializingPow();
}
static class Hash {
static long[] power = new long[STRING_MAX_SIZE];
long[] h = new long[STRING_MAX_SIZE];
static final long p = 271;
static final long mod = 1000000007;
int idx;
public static void initializingPow() {
power[0] = 1;
for(int i = 1; i < STRING_MAX_SIZE; i++)
power[i] = power[i-1]*p%mod;
}
public void add(int c) {
if(idx==0)
h[idx++] = c;
else {
h[idx] = (h[idx-1]*p%mod+c)%mod;
idx++;
}
}
public long get_hash(int l, int r) {
if (l == 0)
return h[r];
return (h[r] - h[l - 1] * power[r - l + 1] % mod + mod) % mod;
}
}
}