[연습] POJ - 3461 Oulipo (KMP / 문자열 해시)

제목
PJ 의 여자 친 구 는 서예가 로 예 쁜 영어 서 예 를 즐겨 쓴다.어느 날 PJ 는 생일 선물 을 주 겠 다 는 메 모 를 받 았 다.PJ 는 자신 이 원 하 는 선물 이 그녀 가 준 것 인지 알 고 싶 어서 자신 이 원 하 는 것 이 쪽지 에 몇 번 나 왔 는 지 보고 싶 었 다.
해제
KMP
일치 하면 K 값 을 선택 하 십시오.일치 하 는 문자열 사이 에 겹 치 는 부분 이 있 기 때문에 일치 하 는 부분 이 발생 한 후에 적당 한 짝 짓 기 K 가 발생 하면 메 인 문자열 포인터 가 되 돌아 오지 않 은 상태 에서 일치 하 는 것 을 보증 할 수 있 습 니 다.예 를 들 어도 무방 하 다.
str
최 장 접두사
next n e x t
A A
null n u l l
-1
AZ A Z
null n u l l
-1
AZA A Z A
A A
0
위의 표 에서 볼 수 있 듯 이 AZA A Z A 의 next n e x t 값 은 0 이다.
따라서 패턴 문자열 이 텍스트 문자열 의 첫 번 째 AZA A Z A 와 일치 할 때 이 위치 가 패턴 문자열 의 첫 번 째 문자 와 같 는 지 확인 해 야 메 인 포인터 가 되 돌아 오지 않 은 상태 에서 계속 진행 할 수 있 습 니 다.
Hash
Hash 를 사용 하면 물 을 비교 하고 하위 문자열 을 차례대로 매 거 하여 Hash 값 이 같 는 지 확인 하면 됩 니 다.
코드
KMP

#include
#include
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int nmax = 1e6+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ull p = 67;
const ull MOD = 1610612741;
char text[nmax],str[nmax];
int t,lentext,lenstr,nxt[nmax];
inline void getnxt(){
    nxt[0] = -1; int k = -1;
    for(int i = 1;i<=lenstr-1;++i){
        while(k>-1 && str[k+1] != str[i]) k = nxt[k];
        if(str[k+1] == str[i]) k++;
        nxt[i] = k;
    }
}
inline int KMP(){
    lentext = strlen(text),lenstr = strlen(str);
    getnxt();
    int k = -1,ans = 0;
    for(int i = 0;i<=lentext-1;++i){
        while(k>-1 && str[k+1] != text[i]) k = nxt[k];
        if(str[k+1] == text[i]) k++;
        if(k == lenstr-1){
//            i = i - lenstr + 1;      
            k = nxt[k];
            ans++;
        }
    }
    return ans;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%s %s",str,text);
        printf("%d
",KMP());
    }
    return 0;
}

Hash

#include
#include
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int nmax = 1e6+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ull p = 67;
const ull MOD = 1610612741;
int t,lentext,lenstr;
char text[nmax],str[nmax];
ull hashtext[nmax],hashstr[nmax],pp[nmax];
inline void init(){
    pp[1] = p; for(int i = 2;i<=1000000;++i) pp[i] = pp[i-1] * p;
}
inline void gethash(){
    hashtext[1] = text[1], hashstr[1] = str[1];
    for(int i = 2;i<=lentext;++i) hashtext[i] = hashtext[i-1] * p + text[i];
    for(int i = 2;i<=lenstr;++i) hashstr[i] = hashstr[i-1] * p + str[i];
}
inline ull subhash(int l, int r){
    return hashtext[r] - hashtext[l-1] * pp[r-l+1];
}
int main(){
    init();
    scanf("%d",&t);
    while(t--){
        scanf("%s %s",str+1,text+1);
        lentext = strlen(text+1), lenstr = strlen(str+1);
        gethash();
        int l = 1,ans=0;
        while(true){
            int r = l +  lenstr -1;
            if(subhash(l,r) == hashstr[lenstr]) ans++;
            l++;
            if(l + lenstr -1 > lentext) break;
        }
        printf("%d
",ans);
    }
    return 0;
}