首页 > 代码库 > 2017 UESTC Training for Search Algorithm & String
2017 UESTC Training for Search Algorithm & String
2017 UESTC Training for Search Algorithm & String
A next[]数组应用
题意：求一个字符串所有前缀出现的次数和。
tags： dp[i-1] = dp[next[i]] + 1。
D 字符串next[]数组
题意：求给出字符串的最短循环节。
tags：看了题解，原来next[]数组可以这样搞。。
思考KMP的next数组的定义：next[j] = i 代表 s[1...(i-1)] = s[j - i, j-1]。 并且i~j之间已经不可能有以j结尾的子串是前缀了，不然next[j]就不是 i 了。那么很显然，字符串的最短循环节长度为 len - next[len]。
#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<queue>#include<stack>#include<map>#include<bitset>#include<vector>#include<set>#include<list>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 1000005;int nex[N];void getnext(char *B, int lenb){ mes(nex, 0); nex[0]=-1; for(int i=0,k=-1; i<lenb; ) { if(k==-1 || B[i]==B[k]) nex[++i]=++k; else k=nex[k]; }}char A[N];int main(){ scanf("%s", A); int len=strlen(A); getnext(A, len); printf("%d\n", len-nex[len]); return 0;}
I dfs，九皇后，水题，但调了好久，还是不熟练啊
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi first#define se secondtypedef long long ll;const int N = 200005;int n, sta[20], top;bool vis1[20], vis2[20], vis3[20], vis4[20];void dfs(int x, int y){ sta[++top]=y; if(top==9) { rep(i,1,top) printf("%d ", sta[i]); puts(""); --top; return ; } vis1[x]=vis2[y]=vis3[x+y]=vis4[y+n-x]=1; rep(i,x+1,n) rep(j,1,n) if(!vis1[i] && !vis2[j] && !vis3[i+j] && !vis4[j+n-i]) { dfs(i, j); } --top; vis1[x]=vis2[y]=vis3[x+y]=vis4[y+n-x]=0;}int main(){ scanf("%d", &n); printf("352\n"); rep(j,1,n) dfs(1, j); return 0;}
2017 UESTC Training for Search Algorithm & String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。