문제 풀이 수업 4 - 1 (hash, 답문 꼬치 문제)

문제 풀이 수업 4 - 1 (hash)
직사각형
  • 두 개의 행렬 을 정 하고 두 번 째 행렬 이 첫 번 째 행렬 에서 어떤 위치 에 나 타 났 는 지 판단 한다
  • 출력 위치의 왼쪽 상단
  • 여러 개의 답 이 있 고 사전 순 으로 출력
  • 해법
  • 한 줄 한 열 비교
  • 매 거 진 두 행렬, n 의 4 차방, 50 의 4 차방 은 1 억 이내
  • 해법
  • 한 행렬 을 하나의 숫자 로 전환시킨다
  • 해시 문자열
  • ebacd
  • hash(ebacd) = (5B^4+2B^3+B^2+3B^1+4B^0) mod mo
    
  • B 는 26 보다 큰 임 의 정수 이 고 질 수 모 를 비교적 큰 질 수
  • 로 취 하 는 것 이 좋다.
  • 이 를 정상 적 인 정수 서열 에 보급 시 키 고 주어진 정수 서열 이 a 라 고 가정 한다.i
  • h a s h ( { a i } ) = ( ∑ i = 1 n a i B n − i )    m o d   m o hash(\{a_i\}) = (\sum_{i=1}^na_iB^{n-i}) \space\space mod \space mo hash({ ai​})=(i=1∑n​ai​Bn−i)  mod mo
  • 그 중에서 B 는 max {a i} 보다 임의의 정수 이 고 표지 판 에서 B 는 233
  • 을 취한 다.
  • 1 차원 을 해결 하고 2 차원
  • 으로 확대 했다.
  • 직사각형 A 를 계산 합 니 다{nXm} 의 hash 값 은 줄 마다 hash 값 을 구하 고 n 개의 hash 값 을 얻 은 다음 n 개의 hash 값 에 대해 1 차원 hash
  • 를 다시 합 니 다.
  • 일반적으로 다음 해시 때 B 는 얼마나 받 습 니까?모
  • 보다 커 야 합 니 다.
  • 충돌 가능성 을 최대한 줄인다 (암호학 에서 충돌 개념 이 있다)
  • B 모 두 세트 를 취하 고 계산 한 hash 1 과 hash 2 가 모두 같다 면 이 두 사각형 이 같다 고 생각 합 니 다
  • 코드 분석
  • mo1 은 1e9 + 7 mo2 는 1e9 + 9 B 로 모두 233 (문제 데이터 수치 범위 이상)
  • 이다.
  • pair 는 이원 조
  • 이다.
  • for (int i = 1; i <= q; i++) {
           
                    p1 = p1 * pw % mo1;
                    p2 = p2 * pw % mo2;
                }
    
  • B ^ q 차방 의 값 을 얻 으 려 면 중간 에 mo 모드
  • 가 필요 합 니 다.
  • p1 = (mo1 - p1) % mo1;
    
  • (mo1 - p1) = (- p1 + mo1) 마지막 으로 요구 하 는 것 은 (- B ^ q) 의 값
  • 이기 때문이다.
  • 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;
                        }
                    }
                }
    
  • j
  • j > = q 일 때 새로 추 가 된 a (i) (j) 를 제외 하고 지난번 에 계 산 된 헤드 값
  • 을 줄 여야 합 니 다.
  • 열 에 따라 hash 값 을 계산 하 는 과정 이 유사 하 다
  • 마지막 으로 답 을 출력 할 때 hash 값 을 저장 하 는 위치 가 오른쪽 아래 에 있 기 때문에 문 제 는 왼쪽 상단 을 출력 해 야 하기 때문에 결 과 는 (i - p + 1, j - q + 1)
  • 이다.
    표준 거리
  • 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;
            }
    }
    

  • 회문집
  • 문자열 을 지정 하여 이 문자열 에 몇 개의 하위 문자열 이 답장 문자열 인지 구하 십시오
  • 하위 문자열 은 문자열 의 연속 부분
  • 답장 문자열 은 원래 문자열 의 역순 으로 이 문자열 과 같 습 니 다
  • 해법
  • 문자열 을 거꾸로 쓴다
  • 매 거 진 문자열 은 O (n2) 이 고 답장 문자열 은 O (n) 이 며 전체적으로 O (n3)
  • 라 고 판단 합 니 다.
    해법
  • 매 거 진 하위 문자열
  • 각 문자열 의 정렬 은 hash 값 을 한 번 계산 하고 역순 은 해시 값 을 한 번 계산 하 며 결 과 는 같다 고 생각 합 니 다
  • .
  • 시간 복잡 도 는 O (n ^ 2)
  • 해법 3 (manacher 알고리즘)
  • 선형 시간 구 해 내기
  • 포맷 + 대칭 성 + 단조 성
  • 회 문 꼬치 길이 에 짝 이 있 으 면 어 떡 하지?
  • 포맷: 문자열 중간 에 같은 문 자 를 삽입 합 니 다
  • 대칭 성, 회 문 꼬치 는 대칭 적 이 고 매번 가장 먼 위 치 를 기록 하 며 대칭 성에 따라 현재 위치 에 있 는 회 문 꼬치 의 길이 (최소 길이)
  • 를 계산한다.
  • 단조 성, 매번 가장 먼 위 치 는 단조 로 운 상승
  • 0
    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
    코드 분석
    커서
  • cur 를 중심 으로
  • i 는 이동 점
  • pos = cur * 2 - i 는 중심 대칭 의 오른쪽 단점 위치 에 관 한 것 이다.
  • int pos = (cur<<1) - i;
                    int now = Math.max(Math.min(len[pos],cur+len[cur]-i),0);
    
  • cur + len (cur) - i 이 점 은 대칭 성 을 통 해 얻 은 최소한 의 회 문 꼬치 길이
  • 를 구한다.
  • while(s[i-now-1] == s[i+now+1]) {
           
                        ++now;
                    }
    
  • 양쪽 으로 확장 시도
  • if (i+now > cur + len[cur]){
           
                        cur = i;
                    }
    
  • cur 를 업데이트 합 니 다. 이전 i + l (i) 은 항상 cur + l (cur)
  • 보다 작 았 기 때 문 입 니 다.
  • 마지막 으로 얻 은 답 은 가장 긴 회 문 꼬치 를 2 로 나 누 어 위로 정리 하 는 것 이다. 바로 이 회 문 꼬치 와 그 하위 꼬치 의 모든 회 문 꼬치 수량
  • 이다.
    표준 거리
  • 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;
            }
    
           
    }
    
  • 좋은 웹페이지 즐겨찾기