[백준] #2866 문자열 잘라내기

문제
꺅!!!! 신촌 알고리즘 캠프에서 배운 해쉬로 푸니까 맞았다!!! 푸는데 꽤 오래걸렸기는 하지만 그래도 뿌듯하다! 몇번 틀렸는데 pow함수를 쓰면 double형으로 반환이 되어서 틀릴 수 있다고 한다. 그래서 pow함수를 직접 구해줘 푸니 맞았다.
a=1,b=2,...z=26으로 두고 곱해줄 임의의 값 x는 x=27으로 둬서 각 행으로 시작하는 접미사 문자열의 해쉬값을 배열에 저장해준다.

3행의 Bx+A가 같다! 이 사진을 힌트로 아래서부터 build up 해나가서 풀면 된다.

• 자료 출처: ICPC Sinchon 2022 Winter Algorithm Camp 임지환 강사님의 String 자료

+) 아 그리고 전역변수로 arr1을 선언해줘야한다. 지역변수로 해주니 자꾸 터져서 전역변수로 고쳐줬다.. 지역변수로 저렇게 큰 배열을 선언해줄 수 없는 것 같다.

#include <iostream>

using namespace std;
char arr[1001][1001];
long long arr1[1001][1001];

int m_pow(int n, int m)
{
    int nn = n;
    for (int i = 0; i < (m-1); i++)
        n *= nn;
    return n;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int r,c;
    int x=27;
    int count=0;
      cin>>r>>c;


    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>arr[i][j];
            
        }
    }
    
    for(int j=0;j<c;j++){
        arr1[r-1][j]=arr[r-1][j]-96;
    }

    

     for(int j=0;j<c;j++){
         for(int i=r-2;i>=0;i--){
             arr1[i][j]=arr1[i+1][j]+(arr[i][j]-96)*m_pow(x,r-i-1);
             
         }
     }

    for(int i=1;i<r;i++){
        for(int j=0;j<c;j++){
            for(int l=j+1;l<c;l++){
               
                if(arr1[i][j]==arr1[i][l]){
                    cout<<count;
                    return 0;
                }

            }
        }
        count++;
    }
    cout<<count;
     

}