c언어 2866번 문자열 잘라내기 (백준)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define P 37
#define M 1000000007
#define m 100003
#define L long long

L calHash(char * s) {
    L a=0,b=1,c;
    while(*s) {
        c=(*s-'a'+1);
        a=(a+c*b)%M;
        b=(b*P)%M;
        ++s;
    } return a;
}

L fast(L base, L exp, L mod) {
	L a=1;
	while(exp>0) {
		if(exp&1) a = (a*base)%mod;
		base = (base*base)%mod;
		exp/=2;
	} return a;
}

int main(void) {
	L v, invP;
    int i,j,r,c,h=0,cnt=0;
    scanf("%d %d",&r,&c);
    char str[c][r+1];
    int hash[c];
    invP = fast(P,M-2,M);
    for(i=0;i<r;i++) for(j=0;j<c;j++) scanf(" %c",&str[j][i]);
    for(i=0;i<c;i++) str[i][r]='\0';
    for(i=0;i<c;i++) hash[i] = calHash(str[i]);
    while(++h < r) {
    	int table[m]={};
    	for(i=0;i<c;i++) {
    		hash[i] = (((hash[i]-(str[i][h-1]-'a'+1))*invP)%M);
    		v=hash[i]%m;
    		while(table[v]) {
    			if(!strcmp(str[i]+h,str[table[v]-1]+h)) {
    				printf("%d",h-1);
    				return 0;
				} else {
					++v; 
					if(v==m) v=0;
				}
			} table[v]=i+1;
		}
	} 
	printf("%d",h-1);
}

 

풀이 : 해쉬 테이블

 

<사용한 것>

calHash : 해쉬값을 구합니다.

처음 문자열에 대한 해쉬값을 구한다음, 시간을 줄이기 위해서, 한 줄 삭제한 다음 다시 해쉬값을 구하는 것이 아니라 기존의 해쉬값에서 약간의 연산만 추가했습니다.

 

(a0P0...anPn)  여기서 a0P0을 제거한 해쉬값은 ( (a0P0...anPn) - a0P0 / P ) mod M 이며 c언어에서 곱셈에 비해 나눗셈은 너무 느리기 때문에 1/P = P^-1 이며 이는 즉 모듈러 역원으로 얻어낼수 있습니다.

 

모듈러 역원 a^-1 = a^(N-2) mod N  (단 N은 소수)  

 

 

fast : 모듈러 역원을 구하기 위한 제곱을 구하는 함수에 mod M  이 추가되었습니다. (밑^지수 에서 지수를 이진수로 바라본 다음, 빨리 a^n 을 구할 수 있는 방법입니다)

 

 

<해쉬값과 해쉬테이블>

해쉬값은 mod M (overflow 방지) 만을 한것을 의미하며, 이러한 해쉬값들을 해쉬테이블에 사용할때는 , 해쉬테이블에 맞게 mod m 을 해주었습니다. 주의 할 점은 해쉬값은 구할때 mod m 을 하지 않습니다. mod m을 한 것은 테이블에 범위에 맞춘 변형된 해쉬값 이라고 보는게 맞습니다.

 

<해쉬테이블 충돌관리>

먼저 특정 변형된 해쉬값을 가지고 이미 어떤 것이 먼저있는지를 확인하고 만약 있다면 strcmp으로 문자열을 비교해 봅니다. 만약 다르다면 (+1) 옆 구역을 확인하며, 같다면 종료합니다.

 

<문자열 입력받기>

문자열을 90도 돌려서 저장하는게 더 편할 것 같아서 %s가 아니라 %c로 각각 문자하나씩 담아서, 90도로 돌려주었습니다.

dobarz
adatak

 

이걸

da\0

od\0

ba\0

at\0

ra\0

zk\0

로 저장했다고 보시면 됩니다 \0은 따로 붙여주었습니다. (for(i=0;i<c;i++) str[i][r]='\0';)

 

https://www.acmicpc.net/problem/2866