【暖*墟】#文字列Hash#文字列Hashと例題

【文字列Hash】
1.特徴と理解
文字グループに発生する位置または回数の問題、すなわち「文字列マッチングの問題」を探します.
2.スクロールハッシュの最適化テクニック
2つの適切な互質数b,h(bを選択する
ハッシュ関数の定義は、H(C)=(c 1*b^(m-1)+c 2*b^(m-2)+....+cm*b^0) mod h.
bを基数とし,H(C)の処理は文字列をb進数と見なすことに相当する.
この過程は再帰的計算によりH(C,k)=H(C,k−1)*b+ckである.
あるセグメントの文字が他の一致列と一致するかどうかを判断します.すなわち、次のように判断します.
(ある文字:位置k+1からの長さnのサブ列C'=ck+1 ck+2….ck+n)
H(C′)=H(C,k+n)−H(C,k)*b^nとH(S)の関係.
----->文字列のすべての接頭辞Hash値を前処理します.
----->O(1)時間内に任意のサブストリングHash値を問い合わせる.
unsigned long longの使用:
型取り2^64に使用できます.このような制限条件に遭遇した場合、unsigned long longタイプを使用することを考えます.
typedef unsigned long long ullと簡潔に宣言できます.ullの範囲は[0,2^64-1]なので.
(2^64:18446744073709551616、すなわち10^19.)
したがって,ullタイプの整数がオーバーフローすると,型取り2^64に相当する.
一方long longの範囲は[-2^63,2^63-1]であり,符号のある63位は数値ではなく「正負」を表す
3.例題と運用
(1) poj3461 Oulipo

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef unsigned long long ull;

/*【Oulipo】poj3461
       s1 s2，  s1 s2      。 */
 
//   Hash    

const int b=13331; //base，  

ull power[1000009]; //  b^n
void init(){
    power[0]=1; //b^0=1
    for(int i=1;i<1000000;i++)
        power[i]=power[i-1]*b; // ull  
}

char s1[10009],s2[1000009];
ull sum[1000009]; //          

int main(){
    init(); int T; cin>>T;
    while(T--){
        scanf("%s%s",s1+1,s2+1); //        
        int n=strlen(s1+1),m=strlen(s2+1);
        sum[0]=0; //          
        for(int i=1;i<=m;i++) //       Hash 
            sum[i]=sum[i-1]*b+(ull)(s2[i]-'A'+1);
        ull s=0;
        for(int i=1;i<=n;i++) //      Hash 
            s=s*b+(ull)(s1[i]-'A'+1); 
        int ans=0;
        for(int i=0;i<=m-n;i++)
            if(s==sum[i+n]-sum[i]*power[n]) ans++;
        printf("%d
",ans);
    }
    return 0;
}

(2)poj2406 Power Strings

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

/*【power strings】poj2406
       1e6    ，              。 */
 
//   Hash    

const int b=131; //base，  
const int mod=10009; //h， mod  
int len;
ull hashs[1001000];

ull cal(int x,ull y){ //y^x
    ull now=1;
    while(x){
        if(x&1) now=(now*y)%mod;
        x>>=1; y=(y*y)%mod;
    }
    return now;
}

bool check(int x){ //x:       
    ll cc=cal(x,(ull)b);
    for(int i=(x<<1);i<=len;i+=x)
        if((hashs[i]-(hashs[i-x]*cc)%mod+mod)%mod!=hashs[x]) 
        // H(C,k+n)-H(C,k)*b^n，         hash     
        //  mod，       
            return false;
    return true;
}

int main(){
    while(1){
        char s[1001000];
        scanf("%s",s+1);
        len=strlen(s+1);
        if(len==1&&s[1]=='.') return 0;
        for(int i=1;i<=len;i++) //  Hash 
            hashs[i]=(hashs[i-1]*b+s[i])%mod;
        for(int i=1;i<=len;i++) //       
        //↓↓↓              ，              
            if(len%i==0 && check(i)){ 
                printf("%d
",len/i); break; 
            }
    }
    return 0;
}

(3)poj2752 -hash

#include 
#include 
#include 
using namespace std;
typedef unsigned long long UL;

UL hashs[400005],mul[400005],K=31,P=1000000031;
char s[400005];

int main(){
    mul[0]=1;
    for(int i=1;i<=400000;i++) //   k^n
        mul[i]=mul[i-1]*K%P;
    while(~scanf("%s", s+1)){
        int n=strlen(s+1);
        for(int i=1;i<=n;i++) // hash   
            hashs[i]=(hashs[i-1]*K+s[i]-'a'+1)%P;
        for(int i=1;i<=n;i++)
            if(hashs[i]==((hashs[n]-(hashs[n-i]*mul[i]%P))+P)%P) //  =  
                printf("%d ", i);
        putchar('
');
    }
    return 0;
}

poj2752 -kmp

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

/*【           】POJ 2752
                       。  */

//              s         。
// n - 1          ， s[next[n-1]] == s[n-1]，
//   s[0,1,2,...,next[n-1]]        。
//    s[next[next[n-1]]] == s[n-1]    ，
//      ，  next[next[.....next[n-1]]] == -1  。
 
int Next[400005],ans[400005];
char str[400005];
int cnt,len;
 
void getNext(){
    Next[0] = -1; //  
    int i = 0, j = -1;
    while (i < len){ //    
        if (j == -1 || str[i] == str[j]){ 
        //↑↑↑          ，        
            i++; j++; Next[i]=j; // next  
        }
        else j = Next[j]; //      next    
    }
}
 
int main(){
    while (scanf("%s", str) != EOF){
        len = strlen(str);
        getNext(); //     next  
        cnt = 0; //       
        int j = Next[len - 1]; // next      
        while (j != -1){ 
            if (str[j] == str[len - 1]) 
                ans[cnt++] = j + 1; //     
            j = Next[j];
        }
        for (int i = cnt - 1; i >= 0; --i)
            printf("%d ", ans[i]); // ans[0]     
        printf("%d
", len);
    }
    return 0;
}

(4)bzoj3916 friends

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include