RK算法

算法 腹黑猫 字符串匹配

/*
    Author: 腹黑猫
*/
#include "iostream"
#include "cstring"
using namespace std;
unsigned int PatternHash(char *Pattern){
    int PatternLength = strlen(Pattern);
    unsigned int Hash = 0;
    for (int i = 0; i < PatternLength; ++i){
        Hash += Pattern[i] << (PatternLength - i - 1);
    }
    return Hash;
}
int Find(char *Text, char *Pattern){
    int TextLength = strlen(Text);
    int PatternLength = strlen(Pattern);
    unsigned int Hash = 0;
    unsigned int PHash = PatternHash(Pattern);
    int Pos = 0;
    for (int i = 0; i < PatternLength; ++i){
        Hash += Text[i] << (PatternLength - i - 1);
    }
    if (Hash != PHash){
        for (int i = 1; i <= TextLength - PatternLength; ++i){
            Hash -= Text[i - 1] << (PatternLength - 1);
            Hash <<= 1;
            Hash += Text[i + PatternLength - 1] << 0;
            if (Hash == PHash){
                Pos = i;
                break;
            }
        }
    }
    return Pos;
}
int main(int argc, char const *argv[]){
    cout << Find("abcdefg", "bc");
    return 0;
}