[关闭]
@fuheimao 2015-08-11T07:14:06.000000Z 字数 726 阅读 31

RK算法

算法 腹黑猫 字符串匹配


  1. /*
  2. Author: 腹黑猫
  3. */
  4. #include "iostream"
  5. #include "cstring"
  6. using namespace std;
  7. unsigned int PatternHash(char *Pattern){
  8. int PatternLength = strlen(Pattern);
  9. unsigned int Hash = 0;
  10. for (int i = 0; i < PatternLength; ++i){
  11. Hash += Pattern[i] << (PatternLength - i - 1);
  12. }
  13. return Hash;
  14. }
  15. int Find(char *Text, char *Pattern){
  16. int TextLength = strlen(Text);
  17. int PatternLength = strlen(Pattern);
  18. unsigned int Hash = 0;
  19. unsigned int PHash = PatternHash(Pattern);
  20. int Pos = 0;
  21. for (int i = 0; i < PatternLength; ++i){
  22. Hash += Text[i] << (PatternLength - i - 1);
  23. }
  24. if (Hash != PHash){
  25. for (int i = 1; i <= TextLength - PatternLength; ++i){
  26. Hash -= Text[i - 1] << (PatternLength - 1);
  27. Hash <<= 1;
  28. Hash += Text[i + PatternLength - 1] << 0;
  29. if (Hash == PHash){
  30. Pos = i;
  31. break;
  32. }
  33. }
  34. }
  35. return Pos;
  36. }
  37. int main(int argc, char const *argv[]){
  38. cout << Find("abcdefg", "bc");
  39. return 0;
  40. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注