HDU3746-KMP循环节

发布时间:2017-3-26 15:17:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU3746-KMP循环节",主要涉及到HDU3746-KMP循环节方面的内容,对于HDU3746-KMP循环节感兴趣的同学可以参考一下。

题目:题目链接   题意:给你一个字符串,要求将字符串的全部字符最少循环2次需要添加的字符数。   例子: abcabc 已经循环2次,添加数为0 abcac 没有循环2次,添加字符abcac。数目为5. abcabcab 已经循环过2次,但第三次不完整,需要添加数为1     next函数求法:   void getnext(const char *s) { int i = 0, j = -1; nextval[0] = -1; while(i != len) { if(j == -1 || s[i] == s[j]) nextval[++i] = ++j; else j = nextval[j]; } }   void getnext(const char *p) //前缀函数(滑步函数) { int i = 0, j = -1; nextval[0] = -1; while(i != len) { if(j == -1 || p[i] == p[j]) //(全部不相等从新匹配 || 相等继续下次匹配) { ++i, ++j; if(p[i] != p[j]) //abcdabce nextval[i] = j; else //abcabca nextval[i] = nextval[j]; } else j = nextval[j]; //子串移动到第nextval[j]个字符和主串相应字符比较 } } 就是求出匹配的串之后,对KMP的循环节和原来的长度比较:   如何利用KMP的next求字符串的循环节   #include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int gcd(int n,int m) { if(n<m) swap(n,m); return n%m==0?m:gcd(m,n%m); } int lcm(int n,int m) { if(n<m) swap(n,m); return n/gcd(n,m)*m; } #define N 100010 int prime[N]; struct node { int x, y; }; bool cmp(const node & a, const node & b) { return a.x > b.x; } void getPrime(); void bash(); void wzf(); void SG(); int QuickMod(int a, int b, int n); char num[N]; int next[N]; int len; void getnext() { int i = 0, j = -1; next[0] = -1; while(i != len) { if(j == -1 || num[i] == num[j]) next[++i] = ++j; else j = next[j]; } } int main() { int t; scanf("%d", &t); while(t--) { scanf("%s", num); len = strlen(num); getnext(); int L = len - next[len]; if(len != L && len%L == 0) printf("0\n"); else { int ans = L - next[len]%L; printf("%d\n", ans); } } return 0; } int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; } void getPrime() { memset(prime, 0, sizeof(prime)); prime[0] = 1; prime[1] = 1; for(int i = 2; i < N; ++i) { if(prime[i] == 0) { for(int j = i+i; j < N; j+=i) prime[j] = 1; } } } void bash(int n, int m) { if(n%(m+1) != 0) printf("1\n"); else printf("0\n"); } void wzf(int n, int m) { if(n > m) swap(n, m); int k = m-n; int a = (k * (1.0 + sqrt(5.0))/2.0); if(a == n) printf("0\n"); else printf("1\n"); } int numsg[N]; void SG(int n) { int sum = 0; for(int i=0; i < n; i++) { scanf("%d",&numsg[i]); sum ^= numsg[i]; } if(sum == 0) printf("No\n"); else { printf("Yes\n"); for(int i = 0; i < n; i++) { int s = sum ^ numsg[i]; if(s < numsg[i]) printf("%d %d\n", numsg[i], s);//从有num[i]个石子的堆后剩余s个石子 } } }  

上一篇:插入排序
下一篇:简单的程序诠释C++ STL算法系列: find & find_if

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款