import
java.util.*;
public
class
Main {
public
static
ArrayList<Integer>
rolling_hash(String s,
int
window_size,
int
base,
int
mod)
{
int
n = s.length();
ArrayList<Integer> power
=
new
ArrayList<Integer>(n +
1
);
ArrayList<Integer> hash_values
=
new
ArrayList<Integer>(n - window_size +
1
);
for
(
int
i =
0
; i <= n; i++) {
power.add(
1
);
}
for
(
int
i =
1
; i <= n; i++) {
power.set(i, (power.get(i -
1
) * base) % mod);
}
int
current_hash =
0
;
for
(
int
i =
0
; i < window_size; i++) {
current_hash
= (current_hash * base + s.charAt(i)) % mod;
}
hash_values.add(current_hash);
for
(
int
i =
1
; i <= n - window_size; i++) {
current_hash = (current_hash
- power.get(window_size -
1
)
* s.charAt(i -
1
))
% mod;
current_hash = (current_hash * base
+ s.charAt(i + window_size -
1
))
% mod;
hash_values.add(current_hash);
}
return
hash_values;
}
public
static
void
main(String[] args)
{
String s =
"abcabcabc"
;
int
window_size =
3
;
ArrayList<Integer> hash_values
= rolling_hash(s, window_size,
26
,
1000000007
);
for
(
int
val : hash_values) {
System.out.print(val +
" "
);
}
System.out.println();
}
}