해시 처리 문자열 일치

질문 A: [해시 와 해시 표] 하위 문자열 찾기
시간 제한: 1 초  메모리 제한: 128 MB 제출: 65  해결: 18 [제출] [상태] [토론 판] [명제 자: admin]
제목 설명
이것 은 템 플 릿 문제 다.문자열 A 와 문자열 B 를 지정 하고 B 가 A 에 나타 나 는 횟수 를 구하 십시오.A 와 B 의 문 자 는 모두 영어 대문자 나 소문 자 이다.A 에서 서로 다른 위치 에 나타 난 B 는 중첩 할 수 있다.
 
입력
문자열 A 와 문자열 B 로 총 두 줄 을 입력 하 십시오.
출력
정 수 를 출력 하면 B 가 A 에서 나타 난 횟수 를 나타 낸다.
샘플 입력

zyzyzyz
zyz

샘플 출력

3

제시 하 다.
1 ≤ A, B 의 길 이 는 ≤ 106, A, B 는 대소 문자 만 포함 합 니 다.
[제출] [상태]
[해시 와 문자열]
문자열 '521' 에 대해 서도 숫자 521 이 라 고 볼 수 있 습 니 다. 두 숫자 문자열 이 같 는 지 확인 하려 면 숫자 로 볼 때 같 는 지 확인 해 야 합 니 다.직접 문자열 을 비교 하면 시간 O (n), 숫자 로 보고 비교 하면 시간 O (1);
문자열 "abc" 에 대해 우 리 는 a 를 1, b 를 2 로 볼 수 있 습 니 다......................................................................그게 하 쉬 의 매력 이 야.이 방식 은 문자열 을 k 진수 로 보 는 것 입 니 다. 이 문자열 의 해시 값 이 라 고 부 릅 니 다. 수치 로 크기 를 비교 하 는 것 이 가장 빠 릅 니 다. 그러나 문자열 의 길 이 는 가끔 길 고 정형 변 수 는 큰 수 를 저장 하기 어렵 기 때문에 우 리 는 M 을 모 아서 저장 합 니 다. 즉, 우리 가 일반적으로 사용 하 는 해시 값 은 M 을 모 아서 저장 합 니 다.그러나 충돌 이 불가피 하 다. 어떤 해시 값 모드 가 M 을 제외 한 다른 문자열 의 해시 값 과 같 을 것 이다.
k 와 M 의 선택 에 대해 대부분의 글 은 대소수 선택 을 강조 합 니 다!하지만 증명 서 는 거의 없다.여기 서 한 편의 관점 은 가능 한 한 크 면 된다 는 것 이다.https://blog.csdn.net/maoliran/article/details/52082829 그리고 이 지인 의 대답 에는 일리 가 있 는 것 같다.https://www.zhihu.com/question/20806796/answer/21359160
그 다음 에 저 는 개인 적 으로 M 이 클 수록 좋 습 니 다. 그 다음 에 k 와 M 은 서로 질 을 해 야 합 니 다!OJ 를 통 해 문 제 를 내 는 것 은 확실히 이렇게 해야만 AC 를 할 수 있다.k 가 M 과 서로 질 을 맞 추 려 면 직접 소수 로 가 는 것 이 가장 좋다.때로는 나눗셈 을 할 수도 있 고 역 원 을 사용 해 야 한다. 그러면 M 은 소수 여야 역 원 이 있다.
[분석]
진 k = 97, M = 2 ^ 64 를 선택 하 십시오. unsigned long 의 자 연 스 러 운 넘 침 으로 이 모드 를 완성 할 수 있 습 니 다.
B 문자열 의 해시 값 을 구하 고 A 에서 창 을 스크롤 합 니 다. 모든 길이 가 B 길이 와 같은 하위 문자열 의 해시 값 과 비교 합 니 다. 같은 것 은 문자열 과 같 습 니 다.
【 코드 】

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX=1e6+5;

const int base=95;
char a[MAX],b[MAX];
unsigned long long getval(char ch)
{
    if(ch>='a'&&ch<='z')return ch-'a'+1;
    return ch-'A'+27;
}

ull sum[MAX];
int main()
{
    scanf("%s%s",a,b);
    int n=strlen(b),m=strlen(a);
    sum[0]=getval(a[0]);
    for(int i=1;i