Rabin_Karp(hash) HDOJ 1711 Number Sequence

题目传送门

 /*

 　　Rabin_Karp：虽说用KMP更好，但是RK算法好理解。简单说一下RK算法的原理：首先把模式串的哈希值算出来，

         在文本串里不断更新模式串的长度的哈希值，若相等，则找到了，否则整个模式串的长度的哈希值向右移动一位

 */

 /************************************************

 * Author        :Running_Time

 * Created Time  :2015-8-5 14:04:26

 * File Name     :HDOJ_1711.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef unsigned long long ull;

 typedef long long ll;

 const int MAXN = 1e6 + ;

 const int MAXM = 1e4 + ;

 const int INF = 0x3f3f3f3f;

 const ull KEY = ;

 int a[MAXN], b[MAXM];

 int n, m;

 int match(void) {

     ull h = ;

     for (int i=; i<m; ++i)    h *= KEY;

     ull ah = , bh = ;

     for (int i=; i<m; ++i)    ah = ah * KEY + a[i];

     for (int i=; i<m; ++i)    bh = bh * KEY + b[i];

     for (int i=; i+m<=n; ++i)    {

         if (ah == bh)   return i + ;

         if (i + m < n) {

             ah = ah * KEY + a[i+m] - a[i] * h;

         }

     }

     return -;

 }

 int main(void)    {     //HDOJ 1711 Number Sequence

     int T;  scanf ("%d", &T);

     while (T--) {

         scanf ("%d%d", &n, &m);

         for (int i=; i<n; ++i)    scanf ("%d", &a[i]);

         for (int i=; i<m; ++i)    scanf ("%d", &b[i]);

         printf ("%d\n", match ());

     }

     return ;

 }

 /*

     题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4194

     给你两个字符串A，B，请输出B字符串在A字符串中出现了几次。

 */

 /************************************************

  * Author        :Running_Time

  * Created Time  :2015-8-5 14:04:26

  * File Name     :ZSTU 4194 字符串匹配

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef unsigned long long ull;

 typedef long long ll;

 const int MAXN = 1e6 + ;

 const int INF = 0x3f3f3f3f;

 const ull KEY = ;

 char t[MAXN], p[MAXN];

 int Rabin_Karp(void) {

     int lent = strlen (t);

     int lenp = strlen (p);

     ull h = ;

     for (int i=; i<lenp; ++i)    h *= KEY;

     ull th = , ph = ; int ret = ;

     for (int i=; i<lenp; ++i)    th = th * KEY + t[i];

     for (int i=; i<lenp; ++i)    ph = ph * KEY + p[i];

     for (int i=; i+lenp<=lent; ++i)    {

         if (th == ph)   {

             ret++;

             for (int j=i; j<=i+lenp-; ++j) {       //找到了一个模式串，不能再用，整个跳过去

                 th = th * KEY + t[j+lenp] - t[j] * h;

             }

             i += lenp - ;  continue;

         }

         if (i + lenp < lent) {

             th = th * KEY + t[i+lenp] - t[i] * h;

         }

     }

     return ret;

 }

 int main(void)    {     //ZSTU 4194 字符串匹配

     while (scanf ("%s %s", t, p) == )  {

         printf ("%d\n", Rabin_Karp ());

     }

     return ;

 }

Rabin_Karp应用

 /*

     这就是赤裸裸的模板题，只不过用数字而已

 */

 /************************************************

 * Author        :Running_Time

 * Created Time  :2015-8-9 19:45:40

 * File Name     :KMP.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 1e6 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 int nex[MAXN];

 int s[MAXN], t[MAXN];

 void get_nex(int lm)    {

     int i = , j = -;   nex[] = -;

     while (i < lm)  {

         if (j == - || t[j] == t[i]) {

             i++;    j++;    nex[i] = j;

         }

         else    j = nex[j];

     }

 }

 int KMP(int ln, int lm)   {

     get_nex (lm);

     int i = , j = ;

     while (i < ln)  {

         while (j != - && s[i] != t[j]) j = nex[j];

         i++;    j++;

         if (j == lm) return (i - j + );

     }

     return -;

 }

 int main(void)    {     //HDOJ 1711 Number Sequence

     int T;  scanf ("%d", &T);

     while (T--)   {

         int ln, lm; scanf ("%d%d", &ln, &lm);

         for (int i=; i<ln; ++i)   scanf ("%d", &s[i]);

         for (int i=; i<lm; ++i)   scanf ("%d", &t[i]);

         printf ("%d\n", KMP (ln, lm));

     }

     return ;

 }

KMP

巴特西

Rabin_Karp(hash) HDOJ 1711 Number Sequence

最新文章

热门文章