문제 풀이 수업 4 - 1 (hash, 답문 꼬치 문제)
직사각형
hash(ebacd) = (5B^4+2B^3+B^2+3B^1+4B^0) mod mo
for (int i = 1; i <= q; i++) {
p1 = p1 * pw % mo1;
p2 = p2 * pw % mo2;
}
p1 = (mo1 - p1) % mo1;
for (int i = 1; i <= n; i++) {
long t1 = 0, t2 = 0;
for (int j = 1; j <= m; j++) {
if (j < q) {
t1 = (t1 * pw + a[i][j]) % mo1;
t2 = (t2 * pw + a[i][j]) % mo2;
} else {
t1 = h1[0][i][j] = (t1 * pw + a[i][j] + p1 * a[i][j - q]) % mo1;
t2 = h2[0][i][j] = (t2 * pw + a[i][j] + p2 * a[i][j - q]) % mo2;
}
}
}
표준 거리
static class Task {
// c++ pair
class pii {
public int first;
public int second;
public pii() {
first = second = 0;
}
public pii(int first, int second) {
this.first = first;
this.second = second;
}
}
final int N = 1005;
final long mo1 = (long) 1e9 + 7; //
final long mo2 = (long) 1e9 + 9;
final long pw = 233; // base
//
// bb: b ，bb[0][i][j] (i,1) (i,j) hash ( mo1) ，bb[1][i][j] (i,1) (i,j) hash ( mo2)
long[][][] h1 = new long[2][N][N];
long[][][] h2 = new long[2][N][N];
long[][][] bb = new long[2][N][N];
// ，
// a, b： ，a (n+1)*(m+1)，b (p+1)*(q+1)， 1 （ 0 ， ）
// n, m, p, q：
// n,m,p,q ， +1 0
int[][] a = new int[N][N];
int[][] b = new int[N][N];
int n, m, p, q;
// a b
// ： pii ，
List<pii> getAnswer() {
// (a+b) % mo = ((a%mo)+(b%mo))%mo
// (a-b) % mo = ((a-b)%mo + mo) % mo // [0,mo-1]
// (a*b) % mo = (a%mo) * (b%mo) %mo
// ， p1,p2 ， ， ( mo1 ， mo2), mo1
// p1 = (-pw^q) % mo1
// pw^q
long p1 = 1, p2 = 1;
for (int i = 1; i <= q; i++) {
p1 = p1 * pw % mo1;
p2 = p2 * pw % mo2;
}
// p1 = ((0-p1)%mo1 + mo1) %mo1
// p1 mo1 ， mo1
// p1 = (mo1-p1) % mo1;
p1 = (mo1 - p1) % mo1;
p2 = (mo2 - p2) % mo2;
// a hash ， h1[0]
// i ，
for (int i = 1; i <= n; i++) {
long t1 = 0, t2 = 0;
// j
for (int j = 1; j <= m; j++) {
// q-1
// n,m=4,p,q=2
//
// [1][1]+[1][2] hash ， [1][2]
if (j < q) {
// ，t1 = a[i][0] pw^(j-2) + a[i][1] pw^(j-3) + ... + a[i][j-2] pw + a[i][j-1]
// ，t1 = a[i][0] pw^(j-1) + a[i][1] pw^(j-2) + ... + a[i][j-1] pw + a[i][j]
// t1 pw ， a[i][j] t1
t1 = (t1 * pw + a[i][j]) % mo1;
t2 = (t2 * pw + a[i][j]) % mo2;
}
// [1][1]+[1][2] [1][2]+[1][3]
else {
// ，t1 = a[i][j-q] pw^(j-1) + a[i][j-q+1] pw^(j-2) + ... + a[i][j-2] pw + a[i][j-1]
// ，t1 = a[i][j-q+1] pw^(j-1) + a[i][j-q+2] pw^(j-2) + ... + a[i][j-1] pw + a[i][j]
// t1 pw ， a[i][j-q] pw^j， a[i][j] t1
t1 = h1[0][i][j] = (t1 * pw + a[i][j] + p1 * a[i][j - q]) % mo1;
t2 = h2[0][i][j] = (t2 * pw + a[i][j] + p2 * a[i][j - q]) % mo2;
}
}
}
// p1 = (-pw^q)%mo1
p1 = 1;
p2 = 1;
for (int i = 1; i <= p; i++) {
p1 = p1 * pw % mo1;
p2 = p2 * pw % mo2;
}
p1 = (mo1 - p1) % mo1;
p2 = (mo2 - p2) % mo2;
// h1[0] hash ， h1[1]，
// j
for (int j = 1; j <= m; j++) {
long t1 = 0, t2 = 0;
// i
for (int i = 1; i <= n; i++) {
if (i < p) {
t1 = (t1 * pw + h1[0][i][j]) % mo1;
t2 = (t2 * pw + h2[0][i][j]) % mo2;
} else {
t1 = h1[1][i][j] = (t1 * pw + h1[0][i][j] + p1 * h1[0][i - p][j]) % mo1;
t2 = h2[1][i][j] = (t2 * pw + h2[0][i][j] + p2 * h2[0][i - p][j]) % mo2;
}
}
}
// b hash ， bb ，
// hash
//
for (int i = 1; i <= p; i++) {
for (int j = 1; j <= q; j++) {
bb[0][i][j] = (bb[0][i][j - 1] * pw + b[i][j]) % mo1;
bb[1][i][j] = (bb[1][i][j - 1] * pw + b[i][j]) % mo2;
}
}
p1 = p2 = 0;
//
// bb b hash ， p1
for (int i = 1; i <= p; i++) {
p1 = (p1*pw+bb[0][i][q])%mo1;
p2 = (p2*pw+bb[1][i][q])%mo2;
}
// ， ( )， ， (i-p+1,j-q+1)
List<pii> ans = new ArrayList<>();
for (int i = p; i <= n; i++) {
for (int j = q; j <= m; j++) {
if (h1[1][i][j] == p1 && h2[1][i][j] == p2) {
ans.add(new pii(i - p + 1, j - q + 1));
}
}
}
return ans;
}
}
회문집
해법
1
2
3
4
5
6
7
8
9
10
11
12
s
%
#
a
#
a
#
b
#
a
#
a
#
$
len
0
0
1
2
1
0
5
0
1
2
1
0
0
cur
0
0
2
3
3
3
6
6
6
6
6
6
0
코드 분석
커서
int pos = (cur<<1) - i;
int now = Math.max(Math.min(len[pos],cur+len[cur]-i),0);
while(s[i-now-1] == s[i+now+1]) {
++now;
}
if (i+now > cur + len[cur]){
cur = i;
}
표준 거리
static class Task {
/* */
final int N = 500005;
char[] s = new char[N*2];
int[] len = new int[N*2];
// str
// ：
long getAnswer(String str) {
int n = str.length();
for (int i = n; i != 0 ; --i) {
s[i<<1] = str.charAt(i-1);
s[i<<1 | 1] = 0;
}
n = n << 1 | 1;
s[1] = 0;
s[0] = 1;
s[n+1] = 2;
// manacher
int cur = 1;
long ans = 0;
for (int i = 2; i <= n; i++) {
// cursor
// i pos cursor
int pos = (cur<<1) - i;
// now pos 0 i 2n ， 0
// now i
int now = Math.max(Math.min(len[pos],cur+len[cur]-i),0);
while(s[i-now-1] == s[i+now+1]) {
++now;
}
// cur+len[cur]
// ，
if (i+now > cur + len[cur]){
cur = i;
}
// now/2
//
ans += Math.ceil(now/2.0);
//
len[i] = now;
}
return ans;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
