문자열 해시 (해시)

문자열 해시 란 숫자 를 만들어 서 유일한 문자열 을 대표 하 는 것 이다.
구조 방법:
만약 당신 에 게 숫자 1166 을 준다 면 형식적 으로 는 그것 이 1 과 6 의 조합 이라는 것 만 알 고 있 지만, 그것 이 대표 하 는 실제 크기 는 1 * 10 ^ 3 + 1 * 10 ^ 2 + 6 * 10 ^ 1 + 6 * 10 ^ 0 이라는 것 을 알 고 있 습 니 다.
같은 이치 로 문자열 을 하나 드 리 겠 습 니 다. 그것 을 숫자 로 바 꾸 려 면 모든 문 자 를 먼저 하나의 숫자 에 대응 한 다음 에 순서대로 진 멱 을 곱 하여 추가 할 수 있 습 니 다.
예 를 들 어 abcd, 우 리 는 각 자모의 ASCII 코드 값 을 a 의 ASCII 코드 값 + 1 을 빼 면 abcd 가 각각 대응 하 는 숫자 1, 2, 3, 4 를 얻 을 수 있 습 니 다. 그 다음 에 23 과 같은 진법 을 취하 여 조합 하면 됩 니 다.보험 은 모든 문자 에 대응 하 는 숫자 (마이너스 상황 은 따로 토론) 보다 진법 이 크다.그렇지 않 으 면 다음 과 같은 상황 이 발생 할 수 있 습 니 다.
a b c d  대응  25. 이때 23 진법 을 취하 면 ab 와 e 의 해시 값 이 같 고 같은 문자열 로 판 단 됩 니 다.
1. 예제: P3370 [템 플 릿] 문자열 해시:https://www.luogu.org/problemnew/show/P3370

#include 

using namespace std;

typedef unsigned long long ULL;    //        

const int N=1e4+5;
const ULL B=29;    //  

ULL hashT[N];      //              
char input[N];

int n,tmp;
int ans;

ULL hashf(char s[])    //        
{
    tmp=0;
    for(int i=0;i>n;
    for(int i=0;i

2. P2957 [USACO09OCT] 곡창 지대 의 메아리 Barn Echoes:https://www.luogu.org/problemnew/show/P2957
 이전 문제 와 달리 우리 가 원 하 는 것 은 문자열 의 해시 값 이 아니 라 문자열 의 '스크롤 해시 값' 입 니 다. 바로 첫 번 째 부터 임의의 하위 문자열 의 해시 값 입 니 다. 그 다음 에 하위 문자열 의 해시 값 을 쉽게 찾 을 수 있 습 니 다.

#include 

using namespace std;

typedef unsigned long long ULL;

const int N=1e3+5;
const ULL B=29;

char s1[N],s2[N];

ULL hashT1[N],hashT2[N];    //               
ULL power[N];               //            

int main()
{
    int ans=0,cnt1=0,cnt2=0;    
    power[0]=1;
    for(int i=1;i<=N;i++) power[i]=power[i-1]*B;
    scanf("%s
%s",s1+1,s2+1);
    int len1=strlen(s1+1);
    int len2=strlen(s2+1);

    for(int i=1;i<=len1;i++)  //                    ，      
        hashT1[i]=hashT1[i-1]*B+(ULL)(s1[i]-'a'+1);
    for(int i=1;i<=len2;i++)
        hashT2[i]=hashT2[i-1]*B+(ULL)(s2[i]-'a'+1);

    ULL hash1,hash2;
    for(int i=1,j=len2; i<=len1&&j>=1; i++,j--)    //                  
    {
        hash1=hashT1[i];
        hash2=hashT2[len2]-hashT2[j-1]*power[i];
        if(hash1==hash2) cnt1=i;       //          ，       ，   i  j        ，i   
    }
    for(int i=len1,j=1; i>=1&&j<=len2; i--,j++)    //                  
    {
        hash1=hashT1[len1]-hashT1[i-1]*power[j];
        hash2=hashT2[j];
        if(hash1==hash2) cnt2=j;
    }
    ans=max(cnt1,cnt2);
    cout<

 3. P1381 단어 암기:https://www.luogu.org/problemnew/show/P1381
 그 블 로그 에서 언급 한http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id = 1813 비슷 하 다.
 사고방식 은 모든 문자열 의 해시 값 을 구하 고 해시 값 + 맵 을 이용 하여 자 를 취 하 는 것 이다.

#include 

using namespace std;

typedef unsigned long long ULL;

const int N=1e3+5;
const int M=1e5+5;
const int L=15;
const int B=29;

char s1[L],s2[L];
ULL hashT1[N];
ULL hashT2[M];

int n,m;

maphaved;        //           
mapwordHave;     //     
mapsumHave;      //                    

int hashf(char s[])
{
    int tmp=0;
    for(int i=0;i>n;
    for(int i=0;i>m;
    int sumWord=0;
    for(int i=0;i1 || wordHave[hashT2[l]]==0)
        {
            haved[hashT2[l]]--;
            l++;
        }
        ans=min(ans,r-l+1);
    }
    cout<