首页 > 代码库 > LA 6439 Pasti Pas! Hash
LA 6439 Pasti Pas! Hash
直接默认hash不会冲突,其实很多现成的字符串hash算法是很优秀的。。。大概率可以水过。。。。
然后从两端往中间搞一搞,特殊处理一下中间的情况就好。
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 50000 + 5;const int mod = 65536;char S[maxn];void solve() { int len = strlen(S); int lb = 0, rb = len - 1; LL lhash = 0,rhash = 0,rp = 1; int ans = 0; bool pp = false; while(lb <= rb) { //BKDRHash lhash = lhash * 131 + S[lb]; rhash = rhash + rp * S[rb]; rp *= 131; if(lhash == rhash) { if(lb == rb) ans++; else ans += 2; lhash = rhash = 0; rp = 1; pp = true; } else pp = false; lb++; rb--; } ans += (int)!pp; printf("%d\n",ans);}int main() { int T; scanf("%d",&T); for(int kase = 1;kase <= T;kase++) { scanf("%s",S); printf("Case #%d: ",kase); solve(); } return 0;}
LA 6439 Pasti Pas! Hash
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。