POJ3461 字符串哈希

发布时间:2017-2-20 0:42:14 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ3461 字符串哈希",主要涉及到POJ3461 字符串哈希方面的内容,对于POJ3461 字符串哈希感兴趣的同学可以参考一下。

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<set> #include<map> #include<queue> #include<vector> #include<stack> using namespace std; #define ll long long #define ull unsigned long long #define mxn 1002000 #define eps 1e-8 char t[mxn], w[mxn]; ull h[mxn], p[mxn]; ull geth( int l, int r ) { return h[r] - h[ l - 1 ] * p[ r - l + 1]; } int main() { int cas; p[0] = 1; for( int i = 1; i < mxn; ++i ) p[i] = p[i-1] * 133; scanf( "%d", &cas ); while( cas-- ) { scanf( "%s", w + 1 ); scanf( "%s", t + 1 ); ull cnt = 0; int wn = strlen( w + 1 ); for( int i = 1; i <= wn; ++i ) cnt = cnt * 133 + w[i]; h[0] = 0; int n = strlen( t + 1 ); for( int i = 1; i <= n; ++i ) h[i] = h[i-1] * 133 + t[i]; int ans = 0; for( int i = 1; i <= n - wn + 1; ++i ) if( cnt == geth( i, i + wn - 1 ) ) ans++; printf( "%d\n", ans ); } return 0; }

上一篇:Codeforces 390A Inna and Alarm Clock(水题)
下一篇:Hadoop Mapreduce multiple Input files

相关文章

相关评论